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

Da jede Fläche von T (S) aus zwei horizontalen Seiten besteht, (wobei eine die Länge 0 haben kann
- wie in der Abbildung 1 -) werden diese Flächen Trapeze genannt. Was ist die Komplexität von T (S)? Falls S aus n Liniensegmenten besteht, gibt es höchstens
2n verschiedene Endpunkte. Zu jedem Endpunkt gehört die horizontale Erweiterung, die höchtens
zwei Knoten in T (S) verursacht. T (S) hat deshalb höchstens 6n Knoten. Außerdem ist dieser Graph
planar und hat deshalb T (S) O(n) Kanten und Flächen. Unserer Algorithmus erfordert, dass jedes Trapez in T (S) höchstens mit jeweils zwei Trapezen
oberhalb und unterhalb benachbart ist. Wir bezeichnen ein Trapez als nicht degeneriert, wenn sei-
ne Ober- bzw. Unterseite sich höchstens über zwei andere Trapezunter- bzw. oberseiten erstreckt.
Diese Eigenschaft wird automatisch eingehalten, wenn die Endpunkte der Liniensegmente in S unter-
schiedliche y-Koordinaten haben. Von nun an nehmen wir an, dass S diese Eigenschaft besitzt. Wie
auch in [CTV] erwähnt, ist diese Eigenschaft keine Einschränkung der Allgemeinheit, da diese Ei-
genschaft durch eine kleine Drehung des Koordinatensystems erzielt werden kann. Die Drehung kann
auch durch ein lexikoographische Anordnung simuliert werden: Haben zwei verschiedene Endpunkte
gleiche y-Koordinaten, dann liegt der Punkt mit der kleineren x-Koordinate tiefer. Abbildung 2: Degenerierte Menge von Liniensegmenten Die degenerierte Menge von Liniensegmenten (Abbildung 2) kann durch Drehung des Koordinaten-
systems oder durch lexikographische Anordnung zu einem nicht degenerierten System umgewandelt
werden (Abbildung 3). Abbildung 3: Degeneration wurde durch Drehung oder lexikographische Anordnung behoben.