Improved Incremental Randomized Delaunay Triangulation.

Olivier Devillers 1
1 PRISME - Geometry, Algorithms and Robotics
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, and small memory occupation. 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 levels below. Point location is done by marching in a triangulation to determine the nearest neighbor of the query at that level, then the march restarts from that neighbor at the level below. Using a small sample (3 %) allows a small memory occupation; the march and the use of the nearest neighbor to change levels quickly locate the query.
Type de document :
Rapport
RR-3298, INRIA. 1997
Liste complète des métadonnées

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

https://hal.inria.fr/inria-00073390
Contributeur : Rapport de Recherche Inria <>
Soumis le : mercredi 24 mai 2006 - 12:41:13
Dernière modification le : samedi 27 janvier 2018 - 01:31:03
Document(s) archivé(s) le : dimanche 4 avril 2010 - 23:44:58

Fichiers

Identifiants

  • HAL Id : inria-00073390, version 1

Collections

Citation

Olivier Devillers. Improved Incremental Randomized Delaunay Triangulation.. RR-3298, INRIA. 1997. 〈inria-00073390〉

Partager

Métriques

Consultations de la notice

235

Téléchargements de fichiers

515