Reconstruction et maillages de sous-variétés
Institution:
NiceDisciplines:
Directors:
Abstract EN:
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.
Abstract FR:
Cette thèse s’intéresse à l’approximation linéaire par morceaux de sous-variétés lisses de R-d. L’objectif principal est de développer des algorithmes qui offrent des garanties théoriques (l’approximant doit être homéomorphe à la sous-variété) et ont une complexité sensible à la dimension intrinsèque k de la sous-variété (l’espace et le temps dépendent exponentiellement de k mais seulement linéairement de d). Les deux questions fondamentales dans ce domaine sont : Reconstruction : étant donné un échantillon suffisamment dense P d’une variété M de dimension k plongée dans Rd, construire une approximation simpliciale de M. Echantillonnage et maillage de sous-variétés : pour un paramètre epsilon et une sous-variété M de Rd qu’on peut interroger à l’aide d’oracles, on veut générer un échantillon P de M et une approximation simpliciale de M. Les principales contributions de cette thèse sont : Des conditions suffisantes pour que le complexe de Delaunay tangent construit sur P soit homéomorphe à M et géométriquement proche de M. Un algorithme de complexité sensible à la dimension intrinsèque permettant de reconstruire M à partir de P sous les conditions et avec les garanties mentionnées ci-dessus. Un algorithme permettant d’échantillonner et mailler M avec des oracles simples. Un contre-exemple à un résultat de Leibon et Letscher. Ce contre-exemple montre qu’il ne suffit pas que P soit dense pour que le nerf d’un diagramme de Voronoï intrinsèque soit une triangulation de M. La notion d’ensemble de points delta-générique. Un tel ensemble admet une triangulation de Delaunay qui reste stable si on perturbe les points P ou la métrique. On montre ensuite que si P est suffisamment dense et générique, la triangulation de Delaunay intrinsèque est égale à la triangulation de Delaunay restreinte à M et également au complexe de Delaunay tangent. On présente également un algorithme pour générer de tels ensembles de points delta-génériques.