Guarding galleries and terrains

Alon Efrat, Sariel Har-Peled

Research output: Contribution to journalArticlepeer-review

74 Scopus citations


Let P be a polygon with n vertices. We say that two points of P see each other if the line segment connecting them lies inside (the closure of) P. In this paper we present efficient approximation algorithms for finding the smallest set G of points of P so that each point of P is seen by at least one point of G, and the points of G are constrained to be belong to the set of vertices of an arbitrarily dense grind. We also present similar algorithms for terrains and polygons with holes.

Original languageEnglish (US)
Pages (from-to)238-245
Number of pages8
JournalInformation Processing Letters
Issue number6
StatePublished - Dec 31 2006

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Signal Processing
  • Information Systems
  • Computer Science Applications


Dive into the research topics of 'Guarding galleries and terrains'. Together they form a unique fingerprint.

Cite this