Skip to Main content Skip to Navigation
Journal articles

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

Jean-Daniel Boissonnat 1 Olivier Devillers 1 Monique Teillaud 1
1 PRISME - Geometry, Algorithms and Robotics
CRISAM - Inria Sophia Antipolis - Méditerranée
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 orderlek Voronoi diagrams, can be done in O(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 lceil(d+1)/2rceil+1 n lfloor(d+1)/2rfloor) and space complexityO(k lceil(d+1)/2rceil n lfloor(d+1)/2rfloor). The algorithm is simple and experimental results are given.
Document type :
Journal articles
Complete list of metadata
Contributor : Olivier Devillers Connect in order to contact the contributor
Submitted on : Friday, September 1, 2006 - 1:48:25 PM
Last modification on : Wednesday, October 30, 2019 - 7:36:17 PM
Long-term archiving on: : Monday, April 5, 2010 - 11:27:08 PM




Jean-Daniel Boissonnat, Olivier Devillers, Monique Teillaud. A semidynamic construction of higher-order Voronoi diagrams and its randomized analysis. Algorithmica, Springer Verlag, 1993, 9 (4), pp.329-356. ⟨10.1007/BF01228508⟩. ⟨inria-00090668⟩



Record views


Files downloads