Skip to Main content Skip to Navigation

Triangulating Smooth Submanifolds with Light Scaffolding

Jean-Daniel Boissonnat 1 Arijit Ghosh 1
1 GEOMETRICA - Geometric computing
CRISAM - Inria Sophia Antipolis - Méditerranée , Inria Saclay - Ile de France
Abstract : We propose an algorithm to sample and mesh a k-submanifold M of positive reach embedded in Rd. 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 developped for meshing surfaces of R^3, the refinement phase does not rely on a subdivision of Rd (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(ε^(−k^2 −k) ) (for fixed M, d and k).
Document type :
Complete list of metadatas

Cited literature [33 references]  Display  Hide  Download
Contributor : Jean-Daniel Boissonnat <>
Submitted on : Monday, June 27, 2011 - 6:15:59 PM
Last modification on : Saturday, January 27, 2018 - 1:30:59 AM
Long-term archiving on: : Wednesday, September 28, 2011 - 2:28:49 AM


Files produced by the author(s)


  • HAL Id : inria-00604004, version 1



Jean-Daniel Boissonnat, Arijit Ghosh. Triangulating Smooth Submanifolds with Light Scaffolding. [Research Report] RR-7660, INRIA. 2011. ⟨inria-00604004⟩



Record views


Files downloads