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
2 Bernoulli Institute for Mathematics and Computer Science and Artificial Intelligence
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.
keyword : Delaunay triangulation stability simplex quality
Document type :
Journal articles
Complete list of metadata

Cited literature [18 references]  Display  Hide  Download

star_cplx.png
star_cplx.png
star_cplx.jpg
star_cplx.jpg
https://hal.inria.fr/hal-01022371
Contributor : Jean-Daniel Boissonnat <>
Submitted on : Tuesday, October 25, 2016 - 9:55:09 PM
Last modification on : Thursday, December 17, 2020 - 4:36:02 PM

Files

Vignette du document
stab1.pdf
Files produced by the author(s)

Identifiers

Collections

INRIA

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⟩

Export

BibTeX TEI DC DCterms EndNote

Share

Metrics

Record views

341

Files downloads

536