A SEMIDYNAMIC CONSTRUCTION OF HIGHER-ORDER VORONOI DIAGRAMS AND ITS RANDOMIZED ANALYSIS

The k-Delaunay tree extends the Delaunay tree introduced in [1], and [2]. It is a hierarchical data structure that allows the semidynamic construction of the higher-order Voronoi diagrams of a finite set of n points in any dimension. In this paper we prove that a randomized construction of the k-Delaunay tree, and thus of all the order less-than-or-equal-to k Voronoi diagrams, can be done in O(n log n + k3n) expected time and O(k2n) expected storage in the plane, which is asymptotically optimal for fixed k. Our algorithm extends to d-dimensional space with expected time complexity O(k[(d+1/2]+1n[(d+1)/2]) and space complexity O(k[(d+1)/2]n[d+1)2]). The algorithm is simple and experimental results are given.