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 metadatas

https://hal.inria.fr/inria-00090668
Contributor : Olivier Devillers <>
Submitted on : Friday, September 1, 2006 - 1:48:25 PM
Last modification on : Wednesday, March 7, 2018 - 10:46:09 AM
Long-term archiving on : Monday, April 5, 2010 - 11:27:08 PM

Identifiers

Collections

Citation

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⟩

Share

Metrics

Record views

294

Files downloads

136