Triangulation (Punktemenge)

Eine Triangulation einer Menge von Punkten P in der Ebene bezeichnet eine Zerlegung der konvexen Hülle der Punktmenge in Dreiecke, wobei die Eckpunkte der Dreiecke genau die Punkte aus P sind. Somit ist die Triangulation ein ebener Dreiecksgraph.

Ist die Menge P in konvexer Lage, so ist die Anzahl der möglichen Triangulationen genau die n − 2-te Catalan-Zahl, wobei n die Anzahl der Punkte in P bezeichnet.

Triangulationen finden beispielsweise in der 3D-Computergrafik Anwendung, wenn geschwungene Flächen, wie z. B. der Kotflügel eines Autos, in Dreiecke zerlegt werden. Bei einer hinreichend großen Zahl von Dreiecken können diese näherungsweise als eben betrachtet werden, was ihre mathematische Behandlung in der Bildverarbeitung vereinfacht.

Oft ist man daran interessiert, eine Triangulation mit besonderen Eigenschaften zu berechnen. Zum Beispiel gibt es die Delaunay-Triangulation, welche stumpfe Dreiecke vermeidet, oder die Minimum-Weight-Triangulation, welche die Gesamtlänge aller Kanten minimiert.