Finding a guard that sees most and a shop that sells most

Otfried Cheong, Alon Efrat, Sariel Har-Peled

Research output: Contribution to journalArticlepeer-review


We present a near-quadratic time algorithm that computes a point inside a simple polygon P in the plane having approximately the largest visibility polygon inside P, and a near-linear time algorithm for finding the point that will have approximately the largest Voronoi region when added to an n-point set in the plane. We apply the same technique to find the translation that approximately maximizes the area of intersection of two polygonal regions in near-quadratic time, and the rigid motion doing so in near-cubic time.

Original languageEnglish (US)
Pages (from-to)545-563
Number of pages19
JournalDiscrete and Computational Geometry
Issue number4
StatePublished - May 2007

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Geometry and Topology
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics


Dive into the research topics of 'Finding a guard that sees most and a shop that sells most'. Together they form a unique fingerprint.

Cite this