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
2 Johann Bernoulli Institute for Mathematics and Computer Science
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.
Keywords : Delaunay triangulation stability perturbation
Type de document :
Article dans une revue
International Journal of Computational Geometry and Applications, World Scientific Publishing, 2014, 24, pp.125 - 152. <10.1142/S021819591450006X>
Liste complète des métadonnées


pert_ball_shell.jpg
pert_ball_shell.jpg
pert_ball_shell.png
pert_ball_shell.png
https://hal.inria.fr/hal-01097086
Contributeur : Jean-Daniel Boissonnat <>
Soumis le : jeudi 18 décembre 2014 - 17:35:05
Dernière modification le : jeudi 9 février 2017 - 15:48:05
Document(s) archivé(s) le : lundi 23 mars 2015 - 17:28:00

Fichiers

flat_pert.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

INRIA

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>

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de
la notice

333

Téléchargements du document

149

Contact


archive-ouverte@inria.fr