On the peeper's Voronoi diagram

F. Aurenhammer and G. Stoeckl

Abstract:

In the peeper's Voronoi diagram for $n$ sites, any point in the plane belongs to the region of the closest site visible from it. Visibility is constrained to a segment on a line avoiding the convex hull of the sites. We show that the peeper's Voronoi diagram attains a size of $\Theta(n^{2})$ in the worst case, and that it can be computed in $O(n^{2})$ time and space.

Reference: F. Aurenhammer and G. Stoeckl. On the peeper's Voronoi diagram. SIGACT News, 22(4):50-59, 1991. [IIG-Report-Series 264, TU Graz, Austria, 1988].