Open guard edges and edge guards in simple polygons

Csaba D. Tóth, Godfried Toussaint, Andrew Winslow

Research output: Contribution to conferencePaper

Abstract

An open edge of a simple polygon is the set of points in the relative interior of an edge. We revisit several art gallery problems, previously considered for closed edge guards, using open edge guards. A guard edge of a poly- gon is an edge that sees every point inside the polygon. We show that every simple non-starshaped polygon ad- mits at most one open guard edge, and give a simple new proof that it admits at most three closed guard edges. We characterize open guard edges, and derive an algorithm that finds all open guard edges of a simple n-gon in O(n) time in the RAM model of computation. Finally, we present lower bound constructions for simple polygons with n vertices that require [n/3] open edge guards, and conjecture that this bound is tight.

Original languageEnglish (US)
Pages54-64
Number of pages11
DOIs
StatePublished - Dec 1 2011
Event23rd Annual Canadian Conference on Computational Geometry, CCCG 2011 - Toronto, ON, Canada
Duration: Aug 10 2011Aug 12 2011

Other

Other23rd Annual Canadian Conference on Computational Geometry, CCCG 2011
CountryCanada
CityToronto, ON
Period8/10/118/12/11

Keywords

  • art gallery
  • illumination
  • mobile guards
  • visibility

ASJC Scopus subject areas

  • Computational Mathematics
  • Geometry and Topology

Fingerprint Dive into the research topics of 'Open guard edges and edge guards in simple polygons'. Together they form a unique fingerprint.

  • Cite this

    Tóth, C. D., Toussaint, G., & Winslow, A. (2011). Open guard edges and edge guards in simple polygons. 54-64. Paper presented at 23rd Annual Canadian Conference on Computational Geometry, CCCG 2011, Toronto, ON, Canada. https://doi.org/10.1007/978-3-642-34191-5_5