HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Journal articles

Delaunay Stability via Perturbations

Jean-Daniel Boissonnat 1 Ramsay Dyer 2 Arijit Ghosh 3
1 GEOMETRICA - Geometric computing
CRISAM - Inria Sophia Antipolis - Méditerranée , Inria Saclay - Ile de France
3 Algorithms and Complexity
MPII - Max-Planck-Institut für Informatik
Abstract : We present an algorithm that takes as input a finite point set in Rm , and performs a perturbation that guarantees that the Delaunay triangulation of the resulting perturbed point set has quantifiable stability with respect to the metric and the point positions. There is also a guarantee on the quality of the simplices: they cannot be too flat. The algorithm provides an alternative tool to the weighting or refinement methods to remove poorly shaped simplices in Delaunay triangulations of arbitrary dimension, but in addition it provides a guarantee of stability for the resulting triangulation.
Document type :
Journal articles
Complete list of metadata

Cited literature [13 references]  Display  Hide  Download

Contributor : Jean-Daniel Boissonnat Connect in order to contact the contributor
Submitted on : Thursday, December 18, 2014 - 5:35:05 PM
Last modification on : Thursday, January 20, 2022 - 5:26:36 PM
Long-term archiving on: : Monday, March 23, 2015 - 5:28:00 PM


Files produced by the author(s)




Jean-Daniel Boissonnat, Ramsay Dyer, Arijit Ghosh. Delaunay Stability via Perturbations. International Journal of Computational Geometry and Applications, World Scientific Publishing, 2014, 24, pp.125 - 152. ⟨10.1142/S021819591450006X⟩. ⟨hal-01097086⟩



Record views


Files downloads