A new duality result concerning Voronoi diagrams

F. Aurenhammer

Abstract:

A new duality between order-$k$ Voronoi diagrams in $E^d$ and convex hulls in $E^{d+1}$ is established. It implies a reasonably simple algorithm for computing the order-$k$ Voronoi diagram for $n$ points in the palne in $O(k^2
n \log n)$ time and optimal $O(k(n-k))$ space.



Reference: F. Aurenhammer. A new duality result concerning Voronoi diagrams. In Proc. $13^{th}$ Ann. ICALP, Lecture Notes in Computer Science, volume 226, pages 21-32, Rennes, France, 1986. Springer Verlag.