Constructing Intrinsic Delaunay Triangulations of Submanifolds - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Rapport (Rapport De Recherche) Année : 2013

Constructing Intrinsic Delaunay Triangulations of Submanifolds

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

Connectez-vous pour contacter l'auteur

Résumé

We describe an algorithm to construct an intrinsic Delaunay triangulation of a smooth closed submanifold of Euclidean space. Using results established in a companion paper on the stability of Delaunay triangulations on $\delta$-generic point sets, we establish sampling criteria which ensure that the intrinsic Delaunay complex coincides with the restricted Delaunay complex and also with the recently introduced tangential Delaunay complex. The algorithm generates a point set that meets the required criteria while the tangential complex is being constructed. In this way the computation of geodesic distances is avoided, the runtime is only linearly dependent on the ambient dimension, and the Delaunay complexes are guaranteed to be triangulations of the manifold.
Nous montrons que, pour toute sous variété M suffisamment régulière de l'espace euclidien et pour tout échantillon P de points de M qui satisfait une condition locale de delta-généricité et de epsilon-densité, P admet une triangulation de Delaunay intrinsèque qui est égale à la triangulation de Delaunay restreinte à M et aussi au complexe de Delaunay tangent. Nous montrons également comment produire de tels ensembles de points.
Fichier principal
Vignette du fichier
RR-8273.pdf (1.16 Mo) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-00804878 , version 1 (26-03-2013)

Identifiants

Citer

Jean-Daniel Boissonnat, Ramsay Dyer, Arijit Ghosh. Constructing Intrinsic Delaunay Triangulations of Submanifolds. [Research Report] RR-8273, INRIA. 2013, pp.54. ⟨hal-00804878⟩
296 Consultations
236 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More