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

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 Connect in order to contact the contributor
Submitted on : Tuesday, October 25, 2016 - 9:55:09 PM
Last modification on : Friday, January 21, 2022 - 4:10:02 AM

Files

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

Identifiers

Collections

INRIA | INRIA2 | UNIV-PARIS-SACLAY

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 Datacite

Share

Metrics

Record views

175

Files downloads

218

Designed by Inria-IES Team : http://hal.inria.fr/    Hosted by HAL : http://hal.archives-ouvertes.fr/