Fully dynamic Delaunay triangulation in logarithmic expected time per operation

Abstract : The Delaunay Tree is a hierarchical data structure that has been introduced in \cite{BT} and analyzed in \cite{deltree,idag}. For a given set of sites S in the plane and an order of insertion for these sites, the Delaunay Tree stores all the successive Delaunay triangulations. As proved before, the Delaunay Tree allows the insertion of a site in logarithmic expected time and linear expected space, when the insertion sequence is randomized. In this paper, we describe an algorithm maintaining the Delaunay Tree under insertions and deletions of sites. This can be done in O(log n) expected time for an insertion and O(loglog n) expected time for a deletion, where n is the number of sites currently present in the strucuture. For deletions, by expected time, we mean averaging over all already inserted sites for the choice of the deleted sites. The algorithm has been effectively coded and experimental results are given.
Type de document :
Article dans une revue
Computational Geometry, Elsevier, 1992, 2 (2), pp.55--80. 〈10.1016/0925-7721(92)90025-N〉
Liste complète des métadonnées

https://hal.inria.fr/inria-00090678
Contributeur : Olivier Devillers <>
Soumis le : vendredi 1 septembre 2006 - 16:08:26
Dernière modification le : jeudi 20 septembre 2018 - 07:54:02
Document(s) archivé(s) le : lundi 5 avril 2010 - 23:27:11

Fichier

Identifiants

Collections

Citation

Olivier Devillers, Stefan Meiser, Monique Teillaud. Fully dynamic Delaunay triangulation in logarithmic expected time per operation. Computational Geometry, Elsevier, 1992, 2 (2), pp.55--80. 〈10.1016/0925-7721(92)90025-N〉. 〈inria-00090678〉

Partager

Métriques

Consultations de la notice

440

Téléchargements de fichiers

205