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
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.
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

Littérature citée [13 références]  Voir  Masquer  Télécharger


https://hal.inria.fr/hal-01097086
Contributeur : Jean-Daniel Boissonnat <>
Soumis le : jeudi 18 décembre 2014 - 17:35:05
Dernière modification le : lundi 20 novembre 2017 - 15:14:02
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

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〉

Partager

Métriques

Consultations de la notice

343

Téléchargements de fichiers

153