The Delaunay Hierarchy - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Article Dans Une Revue International Journal of Foundations of Computer Science Année : 2002

The Delaunay Hierarchy

Olivier Devillers

Résumé

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.
Fichier principal
Vignette du fichier
hal.pdf (206.4 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

inria-00166711 , version 1 (08-08-2007)

Identifiants

Citer

Olivier Devillers. The Delaunay Hierarchy. International Journal of Foundations of Computer Science, 2002, 13, pp.163-180. ⟨10.1142/S0129054102001035⟩. ⟨inria-00166711⟩
516 Consultations
1148 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More