Die Berechnung der Triangulation eines Polygons in fast-linearer Zeit.

Abbildung 6: Aufteilung von P  in Polygone, die leicht zu triangulieren sind.
Diese Klasse von Polygonen lässt sich in Zeit O(n) triangulieren. Die Verfahrensweise wird in [FM]
und [CI] näher erläutert. 3   Algorithmus Für unsere Zwecke setzen wir eine Datenstruktur für die Tarpezzerlegung T (S) voraus, die für jedes
Trapez t T (S) einen Zugri. auf die benachbarten Trapeze in konstanter Zeit ermöglicht. Weiterhin
wird vorausgesetzt, dass T (S) nicht degeneriert ist. Wie auch schon im letzten Abschnitt erwähnt, ist
diese Eigenschaft eingehalten, wenn zwei verschiedene Endpunkte der Liniensegmente verschiedene y-
Koordinaten haben. Dadurch ist gewährleistet, dass jedes Trapez in T (S) höchstens zwei obere bzw.
untere Nachbarn hat. Eine derartige Datenstruktur erlaubt uns eine eIziente Navigation durch T (S),
d. h. wir können eine Kurve C  durch T (S) günstig verfolgen. Die Kosten, die dabei anfallen, sind
proportional zur Komplexität von C plus der Anzahl der Trapeze, die man bei dieser Tour durchläuft.
Wir halten fest, dass die Größe dieser Datenstruktur linear zur Anzahl der Liniensegmente in S ist.
Zusätzlich führen wir eine Suchstruktur Q(S) mit. Q(S) soll uns helfen, für einen beliebigen Punkt p
das Trapez zu finden, das p enthält. Im Allgemeinen ist Q(S) ein gerichteter, azyklischer Graph mit
einem Wurzelknoten und genau einer Senke für jedes Trapez aus T (S). Jeder Knoten, der keine Senke
ist, hat zwei ausgehende Kanten und ist entweder mit dem Etikett X oder Y  versehen. Ist ein Knoten
mit X  gekennzeichnet, ist der Schlüssel dieses Knotens ein Liniensegment aus S. Falls der Knoten
mit Y  versehen ist, hat er eine reelle Zahl als Schlüssel, die für die y-Koordinate eines Endpunktes
eines  Liniensegments  aus  S  steht  (mit  anderen  Worten:  Es  ist  die  horizontale  Erweiterung  durch
diesen Endpunkt). Falls wir nun zu einen beliebigen Punkt q das Trapez aus T (S) suchen, das q enthält, verfahren wir