Skip to Main content Skip to Navigation
Conference papers

Perturbations and Vertex Removal in a 3D Delaunay Triangulation

Olivier Devillers 1 Monique Teillaud 1
1 GEOMETRICA - Geometric computing
CRISAM - Inria Sophia Antipolis - Méditerranée
Abstract : Though Delaunay triangulations are very well known geometric data structures, the problem of the robust removal of a vertex in a three-dimensional Delaunay triangulation is still a problem in practice. We propose a simple method that allows to remove any vertex even when the points are in very degenerate configurations. The solution is available in CGAL (, releases 2.3 and 2.4).
Document type :
Conference papers
Complete list of metadata

Cited literature [16 references]  Display  Hide  Download
Contributor : Olivier Devillers Connect in order to contact the contributor
Submitted on : Friday, December 21, 2012 - 2:45:30 PM
Last modification on : Friday, February 4, 2022 - 3:18:54 AM
Long-term archiving on: : Sunday, December 18, 2016 - 8:31:42 AM


Files produced by the author(s)


  • HAL Id : inria-00166710, version 2



Olivier Devillers, Monique Teillaud. Perturbations and Vertex Removal in a 3D Delaunay Triangulation. Proceedings of the 14th ACM-SIAM Symposium on Discrete Algorithms, 2003, Baltimore, MA, United States. pp.313--319. ⟨inria-00166710v2⟩



Record views


Files downloads