Delaunay triangulation of manifolds - 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 triangulation of manifolds

Résumé

We present an algorithmic framework for producing Delaunay triangulations of manifolds. The input to the algorithm is a set of sample points together with coordinate patches indexed by those points. The transition functions between nearby coordinate patches are required to be bi-Lipschitz with a constant close to 1. The primary novelty of the framework is that it can accommodate abstract manifolds that are not presented as submanifolds of Euclidean space. The output is a manifold simplicial complex that is the Delaunay complex of a perturbed set of points on the manifold. The guarantee of a manifold output complex demands no smoothness requirement on the transition functions, beyond the bi-Lipschitz constraint. In the smooth setting, when the transition functions are defined by common coordinate charts, such as the exponential map on a Riemannian manifold, the output manifold is homeomorphic to the original manifold, when the sampling is sufficiently dense.
Nous présentons un cadre algorithmique pour construire des triangulations de Delaunay de variétés. L'entrée de l'algorithme est un ensemble de points ainsi que que des cartes locales euclidiennes indicées par ses points. Les fonctions de transition entre cartes voisines doivent être bi-Lipschitz avec une constante de Lipschitz proche de 1, mais pas nécessairement lisses. La principale nouveauté de notre approche est de permettre de traiter des variétés abstraites qui ne sont pas des sous-variétés d'un espace euclidien. L'algorithme produit un complexe simplicial qui est le complexe de Delaunay d'un ensemble perturbé des points d'entrée. On peut garantir que le complexe simplicial fourni est une variété. Dans le cas où les fonctions de transition sont lisses et que les cartes locales sont définies par l'application exponentielle sur une variété Riemannienne, le complexe calculé est homéomorphe à la variété originale quand l'échantillonnage est suffisamment dense.
Fichier principal
Vignette du fichier
RR-8389.pdf (623.16 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-00879133 , version 1 (31-10-2013)

Identifiants

Citer

Jean-Daniel Boissonnat, Ramsay Dyer, Arijit Ghosh. Delaunay triangulation of manifolds. [Research Report] RR-8389, INRIA. 2013, pp.28. ⟨hal-00879133⟩
396 Consultations
440 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More