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 metadatas

Cited literature [13 references]  Display  Hide  Download


https://hal.inria.fr/hal-01097086
Contributor : Jean-Daniel Boissonnat <>
Submitted on : Thursday, December 18, 2014 - 5:35:05 PM
Last modification on : Tuesday, April 30, 2019 - 5:14:02 PM
Long-term archiving on: : Monday, March 23, 2015 - 5:28:00 PM

Files

flat_pert.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

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⟩

Share

Metrics

Record views

518

Files downloads

513