On the Peeper's Voronoi diagram
Franz Aurenhammer, Gerd Stöckl · ACM SIGACT News · 1991
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 Θ( n 2 ) in the worst case, and that it can be computed in O ( n 2 )time and space.