Home Bookmarks Papers Blog

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.

Postscript, PDF.


Last modified: Thu Jul 3 12:36:46 CDT 2003