The stability of Delaunay triangulations

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 introduce a parametrized notion of genericity for Delaunay triangulations which, in particular, implies that the Delaunay simplices of δ-generic point sets are thick. Equipped with this notion, we study the stability of Delaunay triangulations under perturbations of the metric and of the vertex positions. We quantify the magnitude of the perturbations under which the Delaunay triangulation remains unchanged.
Document type :
Journal articles
Complete list of metadatas

Cited literature [18 references]  Display  Hide  Download


https://hal.inria.fr/hal-01022371
Contributor : Jean-Daniel Boissonnat <>
Submitted on : Tuesday, October 25, 2016 - 9:55:09 PM
Last modification on : Tuesday, April 30, 2019 - 5:14:02 PM

Files

stab1.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

Jean-Daniel Boissonnat, Ramsay Dyer, Arijit Ghosh. The stability of Delaunay triangulations. International Journal of Computational Geometry and Applications, World Scientific Publishing, 2014, 23 (4-5), pp.303-333. ⟨10.1142/S0218195913600078⟩. ⟨hal-01022371v2⟩

Share

Metrics

Record views

301

Files downloads

405