Triangulating Smooth Submanifolds with Light Scaffolding - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Article Dans Une Revue Mathematics in Computer Science Année : 2011

Triangulating Smooth Submanifolds with Light Scaffolding

Jean-Daniel Boissonnat
  • Fonction : Auteur
  • PersonId : 935453
Arijit Ghosh
  • Fonction : Auteur
  • PersonId : 938794

Résumé

We propose an algorithm to sample and mesh a k-submanifold M of positive reach embedded in $R^d$. The algorithm first constructs a crude sample of M. It then refines the sample according to a prescribed parameter ε , and builds a mesh that approximates M. Differently from most algorithms that have been developed for meshing surfaces of $R^3$, the refinement phase does not rely on a subdivision of $Rˆd$ (such as a grid or a triangulation of the sample points) since the size of such scaffoldings depends exponentially on the ambient dimension d. Instead, we only compute local stars consisting of k-dimensional simplices around each sample point. By refining the sample, we can ensure that all stars become coherent leading to a k-dimensional triangulated manifold M'. The algorithm uses only simple numerical operations. We show that the size of the sample is O(ε−k) and that M' is a good triangulation of M. More specifically, we show that M and M' are isotopic, that their Hausdorff distance is O(ε2) and that the maximum angle between their tangent bundles is O(ε) . The asymptotic complexity of the algorithm is T(ε)=O(ε−k2−k) (for fixed M, d and k).
Vignette du fichier
inconsistent2.png (158.96 Ko) Télécharger le fichier
Vignette du fichier
inconsistent2.jpg (70.92 Ko) Télécharger le fichier
Format : Figure, Image
Origine : Fichiers produits par l'(les) auteur(s)
Format : Figure, Image
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-01108511 , version 1 (22-01-2015)

Identifiants

Citer

Jean-Daniel Boissonnat, Arijit Ghosh. Triangulating Smooth Submanifolds with Light Scaffolding. Mathematics in Computer Science, 2011, 4 (4), pp.431-461. ⟨10.1007/s11786-011-0066-5⟩. ⟨hal-01108511⟩

Collections

INRIA INRIA2
88 Consultations
4 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More