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.
Document type :
Conference papers
Complete list of metadatas

https://hal.inria.fr/hal-01179435
Contributor : Olivier Devillers <>
Submitted on : Wednesday, July 22, 2015 - 2:43:00 PM
Last modification on : Wednesday, July 31, 2019 - 2:32:48 PM

Links full text

Identifiers

Collections

Citation

Olivier Devillers. On deletion in Delaunay triangulations. Proceedings of the 15th Annual Symposium on Computational Geometry, 1999, Miami, United States. pp.181-189, ⟨10.1145/304893.304969⟩. ⟨hal-01179435⟩

Share

Metrics

Record views

233