Übersicht

Das Problem der Triangulierung eines einfachen Polygons ist das Zerlegen dessen in Dreiecke mit Diagonalen. Die Verallgemeinerung, dass in dem Polygon auch Löcher sind, das heißt wieder Polygone, wird Triangulation eines einfachen Polygons mit Löchern genannt.

Zu Beginn der Arbeit wird die Existenz einer Triangulierung für jedes Polygon mit Löchern gezeigt. Danach ein historischer Überblick, welche Möglichkeiten es gibt. Darin ist speziell der Algorithmus von Chazelle hervorgehoben.

Das weitere Ziel der Arbeit ist eine Beschreibung des praktikablen Algorithmus zur Erstellung einer Trapezzerlegung von Seidel und das nachfolgende Triangulieren dieser Dekomposition.

Triangulation eines einfachen Polygons mit Löchern	Trapezzerlegung eines Dreiecks und möglicher Graphdarstellung