A simple on-line randomized incremental algorithm for computing higher order Voronoi diagrams

F. Aurenhammer and O. Schwarzkopf

Abstract:

We present a simple algorithm for maintaining order-$k$ Voronoi diagrams in the plane. By using a duality transform that is of interest in its own right, we show that the insertion or deletion of a site involves little more than the construction of a single convex hull in three-space. In particular, the order-$k$ Voronoi diagram for $n$ sites can be computed in time $O(nk^{2}
\log n + nk \log^{3} n)$ and optimal space $O(k(n-k))$ by an on-line randomized incremental algorithm. The time bound can be improved by a logarithmic factor without losing much simplicity. For $k \geq \log^{2} n$, this is optimal for a randomized incremental construction; we show that the expected number of structural changes during the construction is $\Theta
(nk^{2})$. Finally, by going back to primal space, we obtain a dynamic data structure that supports $k$-nearest neighbor queries, insertions, and deletions in a planar set of sites. The structure promises easy implementation, exhibits a satisfactory expected performance, and occupies no more storage than the current order-$k$ Voronoi diagram.



Reference: F. Aurenhammer and O. Schwarzkopf. A simple on-line randomized incremental algorithm for computing higher order Voronoi diagrams. In Proc. $7^{th}$ Ann. ACM Symp. Computational Geometry, pages 142-151, North Conway, U.S.A., 1991.