Reconstruction Et Maillages de Sous-variétés
N this thesis we address some of the problems in the field of piecewise linear approximation of k-dimensional smooth submanifolds of Euclidean space R-d. 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 ambient Euclidean dimension d. The two standard questions in this field are the following : Manifold reconstruction. From a dense point ample P in R-d, from an unknown smooth k-dimensional submanifold M of Rd, we want to build a simplicial approximation of M with theoretical guarantees. Sampling and meshing manifolds. For a given parameter epsilon and a k-dimensional smooth submanifold, known through some standard oracle, we want to generate a dense sample P of M, according to the prescribed parameter epsilon, and built a simplicial approximation 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 R-d we give sufficient conditions under which the tangential Delaunay compex, built 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 reconstruct smooth k-dimensional manifolds of R-d 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 outledge, 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 epsilon €, the algorithm generates a dense sample of M and a mesh with theoretical guarantees. The algorithm uses only simple numerical operations. We provide a counterexample to the result announced by Lebon and Letscher. We show that density of the sample points on a manifold M alone cannot guarantee that the nerve of the intrinsic Voronoï diagram, i. e. the intrinsic Delaunay triangulation, is homeomorphic to the manifold M.