HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation

Piecewise linear reconstruction and meshing of submanifolds of Euclidean space

Arijit Ghosh 1
1 GEOMETRICA - Geometric computing
CRISAM - Inria Sophia Antipolis - Méditerranée , Inria Saclay - Ile de France
Abstract : In this thesis we address some of the problems in the field of piecewise linear approxima- tion of k-dimensional smooth submanifolds of Euclidean space Rd. The main goal of this thesis was to develop algorithms that solve these problems with theoretical guarantees, i.e. the output being homeomorphic to the submanifold, and also have intrinsic dimension sensitive complexity, i.e. time and space complexity depend exponentially on the intrinsic dimension k of the submanifold and linearly on the the ambient Euclidean dimension d. The two standard questions in this field are the following: • Manifold reconstruction. From a dense point sample P ⊂ Rd , from an unknown smooth k-dimensional submanifold M of Rd, we want to build a simplicial approxi- mation Mˆ ⊂ Rd of M with theoretical guarantees. • Sampling and meshing manifolds. For a given parameter ε and a k-dimensional smooth submanifold, known through some standard oracles, we want to generate a dense sample P ⊂ M, according to the prescribed parameter ε, and built a simplicial approximation Mˆ of M on top of the sample P with theoretical guarantees. In this thesis we try to chip away at both these problems with the following results: • For a dense point sample P of a smooth submanifold M of Rd we give sufficient conditions under which the tangential Delaunay complex, defined in [BF04, Flö03, Fre02], build using the point sample P is homeomorphic and a close geometric approximation of M. • We give an algorithm, whose complexity is intrinsic dimension sensitive, to recon- struct smooth k-dimensional submanifolds of Rd from a dense point sample P using tangential Delaunay complexes. We show, using the above result, that the output is homeomorphic and a close geometric approximation of M. To the best of our knowledge, this is the first certified algorithm for manifold reconstruction whose complexity is intrinsic dimension sensitive. • We give an algorithm to sample and mesh a k-dimensional smooth submanifold M of Rd. According to the prescribed parameter ε, the algorithm generates a dense sample of M and a mesh with theoretical guarantees. The algorithm uses only simple numerical operations. We show that the size of the sample is O(ε−k) and the asymptotic complexity of the algorithm is T (ε) = O(ε−k2−k) (for fixed M, d and k). • We provide a counterexample to the result announced by Liebon and Letscher [LL00]. We show that density of the sample points on a manifold M alone cannot guarantee that the nerve of the intrinsic Voronoi diagram, i.e. the intrinsic Delaunay triangulation, is homeomorphic to the manifold M. • We introduce a parameterized notion of δ-generic point set for Delaunay triangu- lations. We show that Delaunay triangulation of a δ-generic point sample is (1) combinatorially stable under small perturbation of the underlying metric and vertex positions, and (2) simplices of Delaunay triangualtion are well shaped. • Using the stability results of Delaunay triangulations of δ-generic point set,wes how that, for any sufficiently regular submanifold of Euclidean space, and appropriate ε and δ, any sample set which meets a localized δ-generic ε-dense sampling criteria, intrinsic Delaunay triangulation is equal to restricted Delaunay triangulation and tangential Delaunay triangulation, and intrinsic Delaunay triangulation is homeomorphic to the submanifold. We also give a refinement algorithm for generating intrinsic Delaunay triangulations of submanifolds.
Document type :
Complete list of metadata

Cited literature [100 references]  Display  Hide  Download

Contributor : Jean-Daniel Boissonnat Connect in order to contact the contributor
Submitted on : Thursday, December 18, 2014 - 11:05:34 AM
Last modification on : Thursday, January 20, 2022 - 5:26:54 PM
Long-term archiving on: : Monday, March 23, 2015 - 4:34:53 PM


  • HAL Id : hal-01095861, version 1



Arijit Ghosh. Piecewise linear reconstruction and meshing of submanifolds of Euclidean space. Computational Geometry [cs.CG]. Université de Nice Sophia Antipolis, 2012. English. ⟨hal-01095861⟩



Record views


Files downloads