Fenster - Voronoi Diagramme (Abstract)

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. Fenster - Voronoi Diagramme (Abstract). In Tagungsband DMV Jubilaeumstagung, page 52, Bremen, Germany, 1990.