„Triangulation (Punktemenge)“ – Versionsunterschied

Eine Triangulation einer Menge von Punkten P in der Ebene ist ein maximaler ebener geometrischer Graph, dessen Knoten genau die Punkte aus P sind. Alle inneren Gebiete einer Triangulierung sind Dreiecke, während das äußere Gebiet von der konvexen Hülle von P begrenzt wird.

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 Kardinalität von P bezeichnet.

Oft ist man daran interessiert, eine Triangulation mit besonderen Eigenschaft zu berechnen. Zum Beispiel gibt es die Delaunay-Triangulation, welche den kleinsten Winkel maximiert, oder die Minimum-Weight-triangulation, welche die Gesamtlänge aller Kanten minimiert.

Siehe auch

• Delaunay-Triangulation