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

Schließlich wollen wir noch die Beziehung zwischen der Trapezzerlegung und der Triangulation eines
einfachen Polygons herstellen. Diese Beziehung wurde bereits in [FM] und [CI] entdeckt.     Sei  S  =  {s₀, s₁, . . . , s_n-1} eine  Menge  von  Liniensegmenten,  die  eine  geschlossene  Polygonhülle
bilden. Dabei haben s_i und s_i+1 einen gemeinsamen Endpunkt. Für zwei Liniensegmente s_i, s_j S
gilt foldende Bedingung :   s_i n s_j = Ø  , falls |i - j| > 1 (wir betrachten alle Indizes modulo n). Die
Hülle bildet nun ein einfaches  Polygon  P  mit n Ecken.  Um P  zu triangulieren, müssen wir n - 3
kreuzugsfreie Diagonalen finden, die P  in n - 2 Dreicke teilen. Lemma 1  Sei S = {s₀, s₁, . . . , s_n-1} eine Menge von Ecken auf der Hülle eines einfachen Polygons
P. Ist T (S) bekannt, dann kann die Triangulation von P  in Zeit O(n) berechnet werden. Beweis :  Wir nehmen an, dass P  keine Ecken mit gleicher y-Koordinate hat. Wie bereits erwähnt,
lässt sich diese Bedingung ohne Weiteres herstellen, so dass die Allgemeinheit uneingeschränkt bleibt.
Die Berechnung der Triangulation des Polygons P, ausgehend von T (S), geschieht in drei Schritten:
Im ersten Schritt werden alle Trapeze entfernt, die außerhalb von P  liegen. Abbildung 4: T (S) nach dem die äußeren Trapeze entfernt wurden. Überprüfe, ob T (S) Trapeze enthält, die zwei Ecken von P auf verschiedenen Seiten beinhalten. Falls
ein solches Paar existiert, zeichne eine Diagonale zwischen den Ecken. Abbildung 5: Einführung der Diagonalen in die Trapeze. Die eingezeichneten Diagonalen, teilen P  in y-monotone Unterpolygone auf.