https://hal.inria.fr/hal-01179435Devillers, OlivierOlivierDevillersPRISME - Geometry, Algorithms and Robotics - CRISAM - Inria Sophia Antipolis - Méditerranée - Inria - Institut National de Recherche en Informatique et en AutomatiqueOn deletion in Delaunay triangulationsHAL CCSD1999[INFO.INFO-CG] Computer Science [cs]/Computational Geometry [cs.CG]Devillers, Olivier2015-07-22 14:43:002022-02-04 03:19:222015-07-22 14:43:00enConference papers10.1145/304893.3049691This 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.