Skip to Main content Skip to Navigation
Journal articles

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 metadata

Cited literature [18 references]  Display  Hide  Download


https://hal.inria.fr/hal-01022371
Contributor : Jean-Daniel Boissonnat Connect in order to contact the contributor
Submitted on : Tuesday, October 25, 2016 - 9:55:09 PM
Last modification on : Saturday, May 1, 2021 - 3:38:56 AM

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

358

Files downloads

587