On deletion in Delaunay triangulations

Olivier Devillers 1
1 PRISME - Geometry, Algorithms and Robotics
CRISAM - Inria Sophia Antipolis - Méditerranée
Abstract : This paper presents how the space of spheres and shelling may be used to delete a point from a d-dimensional triangu- lation efficiently. In dimension two, if k is the degree of the deleted vertex, the complexity is O( k log k), but we notice that this number only applies to low cost operations, while time consuming computations are only done a linear number of times. This algorithm may be viewed as a variation of Heller’s algorithm [He190, Mid93], which is popular in the geographic information system community. Unfortunately, Heller algorithm is false, as explained in this paper.
Type de document :
Communication dans un congrès
Annual Symposium on Computational Geometry, 1999, Miami, United States. ACM, pp.181-189, 〈http://www.cs.miami.edu/~vjm/SCG99/〉. 〈10.1145/304893.304969〉
Liste complète des métadonnées

https://hal.inria.fr/hal-01179435
Contributeur : Olivier Devillers <>
Soumis le : mercredi 22 juillet 2015 - 14:43:00
Dernière modification le : samedi 27 janvier 2018 - 01:30:53

Lien texte intégral

Identifiants

Collections

Citation

Olivier Devillers. On deletion in Delaunay triangulations. Annual Symposium on Computational Geometry, 1999, Miami, United States. ACM, pp.181-189, 〈http://www.cs.miami.edu/~vjm/SCG99/〉. 〈10.1145/304893.304969〉. 〈hal-01179435〉

Partager

Métriques

Consultations de la notice

173