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

2   Trapezzerlegung In diesem und folgenden Abschnitten arbeiten wir in der euklidischen Ebene mit dem  üblichen
x-y Koordinatensystem. Definition 1  Zwei Liniensegmente in der Ebene heißen kreuzungsfrei, falls ihre Schnittmenge leer
ist, oder aus einem gemeinsamen Endpunkt besteht. Definition 2  Sei  S  eine Menge von  n  kreuzungsfreien und nicht-horizontalen Liniensegmenten in
der Ebene. Für jedes Segment aus S  und jeden Endpunkt p eines Liniensegments zeichnen wir zwei
horizontale Strahlen, die sich nach rechts und links von p  erstrecken, bis sie auf andere Linienseg-
mente in S stoßen. Für jeden Endpunkt p eines Liniensegments bezeichnen wir die zwei horizontalen
Strahlen, die durch p verlaufen, als horizontale Erweiterung durch p. Definition 3  Die Liniensegmente in S bilden zusammen mit ihren horizontalen Erweiterungen einen
planaren Graphen, den wir Trapezzerlegung von S, oder kurz T (S) nennen. Abbildung 1: Trapezzerlegung von 5 Liniensegmenten