Calculer un ε-filet d'un surface hyperbolique

Les surfaces hyperboliques apparaissent naturellement en mathématiques et font donc l'objet d'études approfondies. Cependant, de nombreuses questions n'ont été résolues que pour des surfaces spécifiques. La mise en œuvre d'algorithmes d'approximation sur les surfaces hyperboliques faciliterait alors l'étude de surfaces plus génériques. La première étape d'un tel algorithme d'approximation est d'approcher la géométrie de la surface avec un ensemble de points bien répartis sur la surface, afin que chaque point de la surface soit proche d'un point de l'ensemble. La notion d'ε-filet répond à cette description. Dans cette thèse, nous concevons un algorithme pour calculer un ε-filet d'une surface hyperbolique compacte et sans bord. Notre algorithme utilise la technique du raffinement de Delaunay : à partir d'une triangulation de Delaunay à un seul sommet sur la surface, l'algorithme insère itérativement les centres circonscrits des triangles dont le rayon du cercle circonscrit est strictement supérieur au paramètre ε. Le nombre de points dans un ε-filet d'une surface hyperbolique dépend à la fois de son aire et de sa systole. En particulier, plus la systole est petite, plus le nombre de points est grand. Afin de rompre cette dépendance à la systole sans perdre d'information géométrique importante, nous étendons notre algorithme au calcul de ce que nous appelons un pseudo ε-filet. Nous détaillons l'implémentation de l'algorithme du calcul d'un ε-filet avec la bibliothèque CGAL. Cette bibliothèque garantit un résultat exact, ce qui permet d'utiliser l'ε-filet obtenu comme entrée pour de futurs algorithmes. Nous utilisons des coordonnées rationnelles pour les points afin d'obtenir une efficacité raisonnable. Nos expériences montrent que la complexité temporelle en pratique est sous-linéaire par rapport au nombre de points, alors que la complexité dans le pire des cas est quadratique.