Delaunay stability via perturbations - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Rapport (Rapport De Recherche) Année : 2013

Delaunay stability via perturbations

Jean-Daniel Boissonnat
  • Fonction : Auteur
  • PersonId : 830857
Ramsay Dyer
  • Fonction : Auteur correspondant
  • PersonId : 938488

Connectez-vous pour contacter l'auteur

Résumé

We present an algorithm that takes as input a finite point set in Euclidean space, 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.
On présente un algorithme qui prend en entrée un ensemble fini de points de l'espace euclidien et les perturbent un peu de façon à garantir que la triangulation de Delaunay des points perturbés est stable de manière quantifiable vis à vis de perturbations de la métrique ou de la position des points. L'algorithme offre également une garantie sur la qualité des simplexes : ils ne peuvent pas être trop plats. L'algorithme propose une alternative simple aux techniques de pondération ou de raffinement qui permettent d'éliminer les simplexes plats des triangulations de Delaunay de dimension arbitraire, et fournit en plus une garantie sur la stabilité de la triangulation construite.
Fichier principal
Vignette du fichier
inria_flatpert.pdf (788.96 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-00806107 , version 1 (29-03-2013)
hal-00806107 , version 2 (28-10-2013)

Identifiants

Citer

Jean-Daniel Boissonnat, Ramsay Dyer, Arijit Ghosh. Delaunay stability via perturbations. [Research Report] RR-8275, INRIA. 2013, pp.26. ⟨hal-00806107v2⟩
413 Consultations
518 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More