On Deletion in Delaunay Triangulation

Olivier Devillers 1
1 PRISME - Geometry, Algorithms and Robotics
CRISAM - Inria Sophia Antipolis - Méditerranée
Abstract : This paper present how space of spheres and shelling can be used to delete efficiently a point from d-dimensional triangulation. In 2-dimension, if k is the degree of the deleted vertex, the complexity is O(k\log k), but we notice that this number apply only to low cost operations; time consuming computations are done only a linear number of times. This algorithm can be viewed as a variation of Heller algorithm which is popular in the geographic information system community. Unfortunalty Heller algorithm is false as explained in this paper.
Type de document :
Rapport
RR-3451, INRIA. 1998
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-00073239
Contributeur : Rapport de Recherche Inria <>
Soumis le : mercredi 24 mai 2006 - 12:18:08
Dernière modification le : samedi 27 janvier 2018 - 01:31:29
Document(s) archivé(s) le : dimanche 4 avril 2010 - 23:39:14

Fichiers

Identifiants

  • HAL Id : inria-00073239, version 1

Collections

Citation

Olivier Devillers. On Deletion in Delaunay Triangulation. RR-3451, INRIA. 1998. 〈inria-00073239〉

Partager

Métriques

Consultations de la notice

233

Téléchargements de fichiers

618