The Delaunay Hierarchy

Olivier Devillers 1
1 GEOMETRICA - Geometric computing
CRISAM - Inria Sophia Antipolis - Méditerranée
Abstract : We propose a new data structure to compute the Delaunay triangulation of a set of points in the plane. It combines good worst case complexity, fast behavior on real data, small memory occupation and the possibility of fully dynamic insertions and deletions. The location structure is organized into several levels. The lowest level just consists of the triangulation, then each level contains the triangulation of a small sample of the level below. Point location is done by walking in a triangulation to determine the nearest neighbor of the query at that level, then the walk restarts from that neighbor at the level below. Using a small subset (3%) to sample a level allows a small memory occupation; the walk and the use of the nearest neighbor to change levels quickly locate the query.
Type de document :
Article dans une revue
International Journal of Foundations of Computer Science, World Scientific Publishing, 2002, 13, pp.163-180
Liste complète des métadonnées

Littérature citée [30 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00166711
Contributeur : Olivier Devillers <>
Soumis le : mercredi 8 août 2007 - 19:10:52
Dernière modification le : vendredi 12 janvier 2018 - 11:02:59
Document(s) archivé(s) le : jeudi 8 avril 2010 - 19:12:45

Fichier

hal.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00166711, version 1

Collections

Citation

Olivier Devillers. The Delaunay Hierarchy. International Journal of Foundations of Computer Science, World Scientific Publishing, 2002, 13, pp.163-180. 〈inria-00166711〉

Partager

Métriques

Consultations de la notice

449

Téléchargements de fichiers

479