La surface de Bolza est la surface hyperbolique orientable compacte la plus symétrique de genre 2. Pour tout genre supérieur à 2, il existe une surface orientable compacte construite de manière similaire à la surface de Bolza et ayant le même type de symétries. Nous appelons ces surfaces des surfaces hyperboliques symétriques. Cette thèse porte sur le calcul des triangulations de Delaunay (TD) de surfaces hyperboliques symétriques. Les TD de surfaces compactes peuvent être considérées comme des TD périodiques de leur revêtement universel (dans notre cas, le plan hyperbolique). Une TD est pour nous un complexe simplicial. Cependant, les ensembles de points ne définissent pas tous une décomposition simpliciale d'une surface hyperbolique symétrique. Dans la littérature, un algorithme a été proposé pour traiter ce problème avec l'utilisation de points factices : initialement une TD de la surface est construite avec un ensemble de points connu, puis des points d'entrée sont insérés avec le célèbre algorithme incrémental de Bowyer, et enfin les points factices sont supprimés, si la triangulation reste toujours un complexe simplicial. Pour la surface de Bolza, les points factices sont spécifiés. L'algorithme existant calcule une DT de la surface de Bolza comme une DT périodique du plan hyperbolique, ce qui nécessite de travailler dans un sous-ensemble approprié du plan hyperbolique. Nous étudions les propriétés des TD de la surface de Bolza définies par des ensembles de points contenants l'ensemble proposé de points factices, et nous décrivons en détail une implémentation de l'algorithme incrémentiel pour cette surface. Nous commençons par définir un représentant canonique unique qui est contenu dans un sous-ensemble borné du plan hyperbolique pour chaque face d'une TD de la surface. Nous donnons une structure de données pour représenter une TD de la surface de Bolza via les représentants canoniques de ses faces. Nous détaillons les étapes de la construction d'une telle triangulation et les opérations supplémentaires qui permettent de localiser les points et de retirer des sommets. Nous présentons également les résultats sur le degré algébrique des prédicats nécessaires pour toutes les opérations. Nous fournissons une implémentation entièrement dynamique pour la surface de Bolza, en offrant l'insertion de nouveaux points, la suppression des sommets existants, la localisation des points, et la construction d'objets duaux. Notre implémentation est basée sur la bibliothèque CGAL (Computational Geometry Algorithms Library), et est actuellement en cours de révision pour être intégrée dans la bibliothèque. L'intégration de notre code dans CGAL nécessite que tous les objets que nous introduisons soient compatibles avec le cadre existant et conformes aux standards adoptés par la bibliothèque. Nous donnons une description détaillée des classes utilisées pour représenter et traiter les triangulations hyperboliques périodiques et les objets associés. Des analyses comparatives et des tests sont effectués pour évaluer notre implémentation, et une application simple est donnée sous la forme d'une démonstration CGAL. Nous discutons une extension de notre implémentation à des surfaces hyperboliques symétriques de genre supérieur à 2. Nous proposons trois méthodes pour engendrer des ensembles de points factices pour chaque surface et présentons les avantages et les inconvénients de chaque méthode. Nous définissons un représentant canonique contenu dans un sous-ensemble borné du plan hyperbolique pour chaque face d'une TD de la surface. Nous décrivons une structure de données pour représenter une telle triangulation via les représentants canoniques de ses faces, et donnons des algorithmes pour l'initialisation de la triangulation. Enfin, nous discutons une implémentation préliminaire dans laquelle nous examinons les difficultés d'avoir des prédicats exacts efficaces pour la construction de TD de surfaces hyperboliques symétriques / The Bolza surface is the most symmetric compact orientable hyperbolic surface of genus 2. For any genus higher than 2, there exists one compact orientable surface constructed in a similar way as the Bolza surface having the same kind of symmetry. We refer to this family of surfaces as symmetric hyperbolic surfaces. This thesis deals with the computation of Delaunay triangulations of symmetric hyperbolic surfaces. Delaunay triangulations of compact surfaces can be seen as periodic Delaunay triangulations of their universal cover (in our case, the hyperbolic plane). A Delaunay triangulation is for us a simplicial complex. However, not all sets of points define a simplicial decomposition of a symmetric hyperbolic surface. In the literature, an algorithm has been proposed to deal with this issue by using so-called dummy points: initially a triangulation of the surface is constructed with a set of dummy points that defines a Delaunay triangulation of the surface, then input points are inserted with the well-known incremental algorithm by Bowyer, and finally the dummy points are removed, if the triangulation remains a simplicial complex after their removal. For the Bolza surface, the set of dummy points to initialize the triangulation is given. The existing algorithm computes a triangulation of the Bolza surface as a periodic triangulation of the hyperbolic plane and requires to identify a suitable subset of the hyperbolic plane in which to work. We study the properties of Delaunay triangulations of the Bolza surface defined by sets of points containing the proposed set of dummy points, and we describe in detail an implementation of the incremental algorithm for it. We begin by identifying a subset of the hyperbolic plane that contains at least one representative for each face of a Delaunay triangulation of the surface, which enables us to define a unique canonical representative in the hyperbolic plane for each face on the surface. We give a data structure to represent a Delaunay triangulation of the Bolza surface via the canonical representatives of its faces in the hyperbolic plane. We detail the construction of such a triangulation and additional operations that enable the location of points and the removal of vertices. We also report results on the algebraic degree of predicates needed for all operations. We provide a fully dynamic implementation for the Bolza surface, supporting insertion of new points, removal of existing vertices, point location, and construction of dual objects. Our implementation is based on CGAL, the Computational Geometry Algorithms Library, and is currently under revision for integration in the library. To incorporate our code into CGAL, all the objects that we introduce must be compatible with the existing framework and comply with the standards adopted by the library. We give a detailed description of the classes used to represent and handle periodic hyperbolic triangulations and related objects. Benchmarks and tests are performed to evaluate our implementation, and a simple application is given in the form of a CGAL demo. We discuss an extension of our implementation to symmetric hyperbolic surfaces of genus higher than 2. We propose three methods to generate sets of dummy points for each surface and present the advantages and shortcomings of each method. We identify a suitable subset of the hyperbolic plane that contains at least one representative for each face of a Delaunay triangulation of the surface, and we define a canonical representative in the hyperbolic plane for each face on the surface. We describe a data structure to represent such a triangulation via the canonical representatives of its faces, and give algorithms for the initialization of the triangulation with dummy points. Finally, we discuss a preliminary implementation in which we examine the difficulties of having efficient exact predicates for the construction of Delaunay triangulations of symmetric hyperbolic surfaces

Cette thèse s'intéresse à la génération, à l'utilisation et à l'évaluation des maillages hex-dominants, composés d'hexaèdres et de tétraèdres, dans la cadre de la simulation numérique par la méthode des éléments finis. Les éléments finis hexaédriques sont souvent préférés aux éléments tétraédriques car ils offrent un meilleur ratio entre précision et temps de calcul dans un certain nombre de situations. Cependant, si la génération automatique de maillages tétraédriques est aujourd'hui un domaine bien maîtrisé, ce n'est pas le cas de la génération de maillages hexaédriques alignés avec le bord, qui reste un problème largement ouvert. En l'absence de progrès significatifs, les approches actuelles se contentent de maillages hex-dominants afin de tirer parti des performances supérieures des hexaèdres et de la flexibilité géométrique des tétraèdres, qui rend possible le maillage automatique. Dans une première partie, nous développons des algorithmes robustes pour la génération de maillages hex-dominants à partir de champs de directions, notamment pour l'isolement et le remplissage des régions difficiles à mailler (singularités et autres dégénérescences). Dans la seconde partie, nous essayons de déterminer dans quelles situations et dans quelle mesure les maillages hexaédriques, et hex-dominants générés précédemment, sont plus intéressants que les maillages tétraédriques. Ceci implique spécifiquement d'étudier plusieurs manières d'effectuer des simulations par éléments finis avec les maillages hybrides, dont une approche où nous utilisons des contraintes de continuité pour maillages non-conformes. Pour mesurer l'influence du maillage sur l'approximation des solutions, nous proposons une nouvelle méthode d'échantillonnage pour calculer très efficacement des distances globales entre solutions éléments finis définies sur des domaines compliqués / This thesis focuses on generation, usage and evaluation of hex-dominant meshes, which are made of hexaehedra and tetrahedra, in the context of the finite element method. Hexahedron finite elements are often preferred to tetrahedron elements because they offer a better compromise between accuracy and computation time in certain situations. However, if tetrahedral meshing is a well mastered subject, it is not the case of hexahedral meshing. Generating hexahedral meshes with elements aligned to the borders is still an open and difficult problem. Meanwhile, current automated approaches can use hex-dominant meshes in order to take advantage of both hexahedron accuracy and geometrical flexibility of tetrahedra. In the first part, we develop robust algorithms for the generation of hex-dominant meshes with elements aligned with the borders. Specifically, we propose a method to extract and fill the areas where hexahedral meshing is difficult (singularities and degeneracies). In the second part, we try to identify and to quantify the advantages of hexahedral and hex-dominant meshes over tetrehedral ones. This requires to study various ways to apply the finite element method on hybrid meshes, including one in which we propose to use continuity constraints on hexahedral-tetrahedral non-conforming meshes. To measure the impact of meshes on the finite element accuracy, we develop a new sampling method which allows to compute efficiently global distances between finite element solutions defined on complicated 3D domains