ISSN:
1432-0541
Keywords:
Computational geometry
;
Dynamic algorithm
;
Randomized complexity analysis
;
Orderk Voronoi diagram
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
,
Mathematics
Notes:
Abstract 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+k 3n) 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⌉+1 n ⌊(d+1)/2⌋) and space complexityO(k ⌈(d+1)/2⌉ n ⌊(d+1)/2⌋). The algorithm is simple and experimental results are given.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF01228508
Permalink
