Maillage de variétés avec les triangulations de Coxeter

This thesis addresses the manifold meshing problem in arbitrary dimension. Intuitively, suppose we are given a manifold — such as the interior of a torus — embedded in a space like R9, our goal is to build a mesh of this manifold (for example, a triangulation). We propose three principal contributions. The central one is the manifold tracing algorithm, which constructs a piecewise-linear approximation of a given compact smooth manifold of dimension m in the Euclidean space Rd, for any m and d. The proposed algorithm operates in an ambient triangulation T that is assumed to be an affine transformation of the Freudenthal-Kuhn triangulation of Rd. It is output-sensitive and its time complexity per computed element in the output depends only polynomially on the ambient dimension d. It only requires the manifold to be accessed via an intersection oracle that answers if a given (d − m)-dimensional simplex in Rd intersects the manifold or not. As such, this framework is general, as it covers many popular manifold representations such as the level set of a multivariate function or manifolds given by a point cloud. Our second contribution is a data structure that represents the Freudenthal-Kuhn triangulation of Rd. At any moment during the execution, this data structure requires at most O(d2) storage. With this data structure, we can access in a time-efficient way the simplex that contains a given point, the faces and the cofaces of a given simplex. The simplices in the Freudenthal-Kuhn triangulation of Rd are encoded using a new representation that generalizes the representation of the d-dimensional simplices introduced by Freudenthal. Lastly, we provide a geometrical and combinatorial study of the Freudenthal-Kuhn triangulations and the closely-related Coxeter triangulations. For Coxeter triangulations, we establish that the quality of the simplices in all d-dimensional Coxeter triangulations is O(1/sqrt{d}) of the quality of the d-dimensional regular simplex. We further investigate the Delaunay property for Coxeter triangulations. Finally, we consider an extension of the Delaunay property, namely protection, which is a measure of non-degeneracy of a Delaunay triangulation. In particular, one family of Coxeter triangulations achieves the protection O(1/d2). We conjecture that both bounds are optimal for triangulations in Euclidean space.Cette thèse s’adresse au problème du maillage d’une variété donnée dans une dimension arbitraire. Intuitivement, on peut supposer que l’on s'est donné une variété — par exemple l’intérieur d’un tore plongé dans R9, et notre objectif est de construire un maillage de cette variété (par exemple une triangulation). Nous proposons trois contributions principales. La première est l’algorithme du tracé des variétés qui reconstruit un complexe cellulaire approchant une variété compacte et lisse de dimension m dans l’espace Euclidien Rd, pour m et d arbitraires. L’algorithme proposé utilise une triangulation T qui est supposé être une transformation linéaire de la triangulation de Freudenthal-Kuhn de Rd. La complexité dépend linéairement de la taille de la sortie dont chaque élément est calculé en temps seulement polynomial en la dimension ambiante d. Cet algorithme nécessite que la variété soit connue par un oracle d’intersection qui répond si un simplexe (d−m)-dimensionnel donné intersecte la variété. À ce titre, ce cadre est général et couvre plusieures représentations des variétés populaires, telles que le niveau d’une fonction multivariée ou les variétés données par un nuage de points. Notre deuxième contribution est une structure de données qui représente la triangulation de Freudenthal-Kuhn de Rd. À chaque étape de l’exécution, l’espace utilisé par la structure de données est au plus O(d2). La structure de données supporte plusieurs opérations d’une manière efficace telles que la localisation d’un point dans la triangulation et accès aux faces et cofaces d’un simplexe donné. Les simplexes dans une triangulation de Freudenthal-Kuhn de Rd sont encodés par une nouvelle représentation qui généralise celle de Freudenthal pour les simplexes d-dimensionels. Enfin, nous étudions la géométrie et la combinatoire des deux types de triangulations étroitement liés : des triangulations de Freudenthal-Kuhn et des triangulations de Coxeter. Pour les triangulations de Coxeter, on démontre que la qualité des simplexes d-dimensionels est O(1/ \sqrt{d}) comparé au simplexe régulier. Par ailleurs, nous établissons lesquelles des triangulations sont de Delaunay. Nous considérons aussi l’extension de la propriété d’être Delaunay qui s’appelle la protection et qui mesure la généricité de la triangulation de Delaunay. En particulier, nous montrons qu’une famille de triangulations de Coxeter atteint la protection O(1/d2). Nous proposons une conjecture que les deux bornes sont optimales pour les triangulations de l’espace Euclidien