Skip to Main content Skip to Navigation
Journal articles

Perturbations for Delaunay and weighted Delaunay 3D Triangulations

Olivier Devillers 1 Monique Teillaud 1
1 GEOMETRICA - Geometric computing
CRISAM - Inria Sophia Antipolis - Méditerranée , Inria Saclay - Ile de France
Abstract : The Delaunay triangulation and the weighted Delaunay triangulation are not uniquely defined when the input set is degenerate. We present a new symbolic perturbation that allows to always define these triangulations in a unique way, as soon as the points are not all coplanar. No flat tetrahedron exists in the defined triangulation. The perturbation scheme is easy to code; It is implemented in CGAL, and guarantees that both vertex insertion and vertex removal are fully robust.
Document type :
Journal articles
Complete list of metadata

Cited literature [21 references]  Display  Hide  Download
Contributor : Olivier Devillers Connect in order to contact the contributor
Submitted on : Friday, January 28, 2011 - 11:28:54 AM
Last modification on : Wednesday, October 30, 2019 - 7:36:17 PM
Long-term archiving on: : Tuesday, November 6, 2012 - 12:31:06 PM


Files produced by the author(s)




Olivier Devillers, Monique Teillaud. Perturbations for Delaunay and weighted Delaunay 3D Triangulations. Computational Geometry, Elsevier, 2011, 44, pp.160--168. ⟨10.1016/j.comgeo.2010.09.010⟩. ⟨inria-00560388⟩



Les métriques sont temporairement indisponibles