Algorithmes pour des surfaces topologiques et métriques

Dans cette thèse, nous fournissons des algorithmes pour des problèmes géométriques et topologiques. Cette ligne de recherche, la géométrie algorithmique, a émergé dans les années 70 avec l’avènement des ordinateurs. Nous considérons le problème du démêlage de graphes sur les surfaces : étant donné un dessin d’un graphe sur une surface, éventuellement avec des croisements, nous devons supprimer tous les croisements en déformant le dessin continuellement, ou affirmer correctement que ce n’est pas possible. Nous donnons les premiers algorithmes en temps polynomial pour ce problème. Pour ce faire, nous introduisons un nouveau type de triangulations de surfaces qui discrétisent les surfaces à courbure négative d’une façon meilleure que l’état de l’art. Sur ces triangulations, nous fournissons un analogue combinatoire des célèbres plongements barycentriques de Tutte. Dans un cadre plus géométrique, nous donnons un nouvel algorithme efficace pour calculer une triangulation de Delaunay d’une surface abstraite plate par morceaux (une généralisation des maillages). Nous étudions également l’algorithme classique de bascule de Delaunay et prouvons, lorsque la surface est un tore plat, la première borne dans le pire cas qui soit optimale à facteur constant près. Sur les surfaces hyperboliques, nous fournissons une implémentation de l’algorithme de bascule de Delaunay, collectée dans un package de la bibliothèque standard de géométrie algorithmique CGAL, et accompagnée d’outils de génération et de visualisation pratiques