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. Int'l Journal of Computational Geometry & Applications, 2:363-381, 1992. Special Issue. [Report B 91-02, FU Berlin, Germany, 1991].