Piecewise linear reconstruction and meshing of submanifolds of Euclidean space

Reconstruction et Maillages de Sous-Variétés

Arijit Ghosh (1)

1 GEOMETRICA - Geometric computing

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.

Cette thèse porte sur la reconstruction de sous-variétés lisses de l'espace euclidien Rd. Elle propose un algorithme essentiellement sensible à la dimension intrinsèque de la variété et qui ne dépend que linéairement de la dimension ambiante. La thèse étudie aussi la stabilité de la triangulation de Delaunay.

Mots clés: Delaunay complex; Intrinsic Delaunay complex; Manifold reconstruction; Mesh generation; Slivers; Stability of Delaunay triangulation

Mots clés: Reconstruction de variétés

Domaines: Géométrie algorithmique [cs.CG]

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