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. Discrete & Computational Geometry, 5(3):243-254, 1990. [IIG-Report-Series 216, TU Graz, Austria, 1985].