Triangulation d'un ensemble de points

Une triangulation d'un ensemble de points P dans le plan est une triangulation de l’enveloppe convexe de P, tous les points de P formant alors des sommets de cette triangulation. Les triangulations sont un sous-ensemble de graphes planaires simples.

Il y a des triangulations particulières, telles que la triangulation de Delaunay qui forme le dual géométrique du diagramme de Voronoï. Parmi les sous-ensembles des triangulations de Delaunay, on peut noter le graphe de Gabriel, le graphe des plus proches voisins et l’arbre couvrant de poids minimal.

Les triangulations se retrouvent dans de nombreuses applications, on peut être amené à chercher la « bonne » triangulation pour un ensemble de points donné suivant certains critères, par exemple, une triangulation de poids^[1] minimal. De temps en temps, on peut aussi rechercher des triangulations ayant des propriétés particulières, par exemple pour laquelle tous les triangles ont de grands angles (en évitant donc tout triangle long et étroit aplati).

Triangulation et enveloppe convexe

Une triangulation d'un ensemble de points E en position générale^[2] peut dériver de l’enveloppe convexe d'un ensemble de points E1 dans l'espace d'une dimension plus élevée qui est composé des projections de l'ensemble E sur la surface paraboloïde d'équation $x_{n+1} = x_1^2+...+x_n^2$. On construit alors l'enveloppe convexe de l'ensemble E1 et on la projette sur l'espace de E. Si les points ne sont pas en position générale, on doit ensuite triangulariser les facettes non-tétrahédriques.

Articles connexes

• Triangulation d'un polygone
• Triangulation de graphe

Notes et références

• (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Point set triangulation » (voir la liste des auteurs)

1. ↑ On peut définir comme poids d'une triangulation d'un ensemble de points dans un plan euclidien comme la somme des longueurs des arêtes la composant.
2. ↑ En géométrie algébrique, la position générale est une position essayant d'éviter tout cas particulier pour se rapprocher du cas générique, on pourrait la rapprocher du sens commun de l'expression pris au hasard.