Skip to Main content Skip to Navigation
New interface

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.
Document type :
Complete list of metadata

Cited literature [1 references]  Display  Hide  Download
Contributor : Rapport De Recherche Inria Connect in order to contact the contributor
Submitted on : Wednesday, May 24, 2006 - 12:18:08 PM
Last modification on : Friday, February 4, 2022 - 3:18:41 AM
Long-term archiving on: : Sunday, April 4, 2010 - 11:39:14 PM


  • HAL Id : inria-00073239, version 1



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



Record views


Files downloads