Guarding simple polygons with semi-open edge guards

Asish Mukhopadhyay; Chris Drouillard; Godfried Toussaint

Guarding simple polygons with semi-open edge guards

Asish Mukhopadhyay, Chris Drouillard, Godfried Toussaint

Computer Science

Research output: Contribution to conference › Paper › peer-review

Abstract

In this note we explore an upper bound on the number of semi-open guard edges in a non star-shaped polygon and provide a characterization to detect semi-open guard edges. Based on this characterization we propose an O(n) time algorithm to find all semi-open guard edges in a polygon.

Original language	English (US)
Pages	417-422
Number of pages	6
State	Published - 2013
Event	3rd International Conference on Digital Information Processing and Communications, ICDIPC 2013 - Dubai, United Arab Emirates Duration: Jan 30 2013 → Feb 1 2013

Other

Other	3rd International Conference on Digital Information Processing and Communications, ICDIPC 2013
Country/Territory	United Arab Emirates
City	Dubai
Period	1/30/13 → 2/1/13

Keywords

Art-gallery problems
Edge guards
Geometric algorithms
Visibility

ASJC Scopus subject areas

Computer Networks and Communications
Information Systems
Signal Processing

Cite this

@conference{daf4eb6b13ba4d498ece03b5a104acd6,

title = "Guarding simple polygons with semi-open edge guards",

abstract = "In this note we explore an upper bound on the number of semi-open guard edges in a non star-shaped polygon and provide a characterization to detect semi-open guard edges. Based on this characterization we propose an O(n) time algorithm to find all semi-open guard edges in a polygon.",

keywords = "Art-gallery problems, Edge guards, Geometric algorithms, Visibility",

author = "Asish Mukhopadhyay and Chris Drouillard and Godfried Toussaint",

note = "Funding Information: The work of the first author was supported by an NSERC Discovery Grant. Research of the third author was supported by a grant from the Provost's Office of New York University Abu Dhabi, through the Faculty of Science, in Abu Dhabi, United Arab Emirates. Publisher Copyright: {\textcopyright} 2013 SDIWC.; 3rd International Conference on Digital Information Processing and Communications, ICDIPC 2013 ; Conference date: 30-01-2013 Through 01-02-2013",

year = "2013",

language = "English (US)",

pages = "417--422",

}

TY - CONF

T1 - Guarding simple polygons with semi-open edge guards

AU - Mukhopadhyay, Asish

AU - Drouillard, Chris

AU - Toussaint, Godfried

N1 - Funding Information: The work of the first author was supported by an NSERC Discovery Grant. Research of the third author was supported by a grant from the Provost's Office of New York University Abu Dhabi, through the Faculty of Science, in Abu Dhabi, United Arab Emirates. Publisher Copyright: © 2013 SDIWC.

PY - 2013

Y1 - 2013

N2 - In this note we explore an upper bound on the number of semi-open guard edges in a non star-shaped polygon and provide a characterization to detect semi-open guard edges. Based on this characterization we propose an O(n) time algorithm to find all semi-open guard edges in a polygon.

AB - In this note we explore an upper bound on the number of semi-open guard edges in a non star-shaped polygon and provide a characterization to detect semi-open guard edges. Based on this characterization we propose an O(n) time algorithm to find all semi-open guard edges in a polygon.

KW - Art-gallery problems

KW - Edge guards

KW - Geometric algorithms

KW - Visibility

UR - http://www.scopus.com/inward/record.url?scp=84920655098&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84920655098&partnerID=8YFLogxK

M3 - Paper

AN - SCOPUS:84920655098

SP - 417

EP - 422

T2 - 3rd International Conference on Digital Information Processing and Communications, ICDIPC 2013

Y2 - 30 January 2013 through 1 February 2013

ER -

Guarding simple polygons with semi-open edge guards

Abstract

Other

Keywords

ASJC Scopus subject areas

Other files and links

Fingerprint

Cite this