On Finding a Guard that Sees Most and a Shop that Sells Most

Otfried Cheong,
Alon Efrat and Sariel Har-Peled

We present a near-quadratic time algorithm that computes a point
inside a simple polygon P having approximately the largest
visibility polygon inside P, and near-linear time algorithm for
finding the point that will have approximately the largest Voronoi
region when added to an n-point set.