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.
Type de document :
Article dans une revue
Algorithmica, Springer Verlag, 1993, 9 (4), pp.329-356. 〈10.1007/BF01228508〉
Liste complète des métadonnées

https://hal.inria.fr/inria-00090668
Contributeur : Olivier Devillers <>
Soumis le : vendredi 1 septembre 2006 - 13:48:25
Dernière modification le : mercredi 7 mars 2018 - 10:46:09
Document(s) archivé(s) le : lundi 5 avril 2010 - 23:27:08

Fichier

Identifiants

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〉

Partager

Métriques

Consultations de la notice

269

Téléchargements de fichiers

113