Triangulation d'un polygone

En géométrie algorithmique, la triangulation d'un polygone consiste à décomposer ce polygone en un ensemble (fini) de triangles. Une triangulation d'un polygone P est une partition de P en un ensemble de triangles qui ne se recouvrent pas, et dont l'union est P. Dans le cas le plus restrictif, on impose que les sommets des triangles ne soient que les sommets de P. Dans un cadre plus permissif, on peut rajouter des sommets à l'intérieur de P ou sur la frontière pour servir de sommets aux triangles. Les triangulations sont des cas particuliers de graphes planaires rectilignes (i. e. dont les arêtes sont des segments). La triangulation d'un polygone convexe est triviale et se calcule en un temps linéaire, par exemple en partant d'un sommet et en ajoutant des arêtes avec tous les autres sommets. En 1991, Bernard Chazelle montra que tout polygone simple peut être triangulé en un temps linéaire. L'algorithme proposé est cependant très complexe, et des algorithmes plus simples sont toujours recherchés. thumb|alt=Une oreille d'un polygone|Une oreille d'un polygone. Une manière de trianguler un polygone simple est d'utiliser le fait que tout polygone simple à au moins quatre sommets possède au moins deux « oreilles », résultat démontré initialement par Max Dehn en 1899 puis oublié jusqu'à être redémontré en 1975. Une oreille est un triangle avec deux arêtes appartenant à la frontière du polygone, et la troisième située à l'intérieur du polygone. L'algorithme consiste à trouver une telle oreille, à la retirer du polygone, ce qui donne un nouveau polygone qui répond toujours aux conditions, et à répéter l'opération jusqu'à ce qu'il n'y ait plus qu'un seul triangle. Cet algorithme est simple à implémenter, mais sous-optimal : une implémentation qui stocke des listes séparées de sommets pour les triangles et le polygone aura une complexité en O(n). thumb|alt=Décomposition d'un polygone en polygones monotones|Décomposition en polygones monotones.