vignette|Deux triangulations différentes du même ensemble de 9 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 poidsOn 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. 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éraleEn 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. 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 . 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 trianguler les facettes non-tétraédriques.
Notes et références
Voir aussi Articles connexes Triangulation d'un polygone Triangulation de graphe
Catégorie:Géométrie discrète Catégorie:Géométrie algorithmique Catégorie:Graphe géométrique Ensemble
de:Gitter (Geometrie)#Dreiecksgitter