A semidynamic construction of higher-order voronoi diagrams and its randomized analysis

Thek-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 ofn points in any dimension. In this paper we prove that a randomized construction of thek-Delaunay tree, and thus of all the order=k Voronoi diagrams, can be done inO(n logn+k3n) expected time and O(k2n) expected storage in the plane, which is asymptotically optimal for fixedk. Our algorithm extends tod-dimensional space with expected time complexityO(k?(d+1)/2?+1n?(d+1)/2?) and space complexityO(k?(d+1)/2?n?(d+1)/2?). The algorithm is simple and experimental results are given.