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

    Bevor wir den Algorithmus präsentieren, müssen wir noch ein paar Worte zur Notation verlieren.
Im Folgenden bezeichnet log⁽ⁱ⁾ den i-ten iterierten Logarithmus, d.h. log⁽⁰⁾ n = n und für i > 0 gilt
log⁽ⁱ⁾ n = log(log^(i-1) n). Für n > 0 bezeichne log^* n die größte natürliche Zahl l, so dass log^(l) n = 1,
und für n > 0 und 0 = h = log^* n sei N(h) die Abkürzung für [n/ log^(h) n]. Welche Größenordnung
hat log^* n ? Nun für ”praktische” Werte von n kann log^* n als Konstante angesehen werden. So ist
zum Beispiel log^* n = 5 für alle n = 10²⁰⁰⁰⁰.     Die Eingabe für den unteren Algorithmus ist eine einfache, polygonale Kette C  bestehend aus n
aufeinanderfolgenden Liniensegmenten entlang C. 1.  Erzeuge s₁, . . . , s_n eine zufällige Reihenfolge der Liniensegmente aus C. 2.  Erzeuge die Trapezzerlegung T₁ und die dazugehörige Suchstruktur Q₁ für die Menge {s₁}. 3.  for h = 1 to log^* n do 3.1.  for N(h - 1) < i = N(h) do 3.1.1.  Ermittle die Trapezzerlegung T_i  und die Suchstruktur Q_i  aus T_i-1 und Q_i-1, durch               Einfügen des Liniensegments s_i.
3.2.  Verfolge C  entlang T_N (h), um für jeden Endpunkt der noch nicht eingefügten Linienseg- mente das zugehörige Trapez in T_N (h). 4.  for N(log^* n) < i = n do 4.1.  Ermittle  die  Trapezzerlegung  T_i  und  die  Suchstruktur  Q_i  aus  T_i-1  und  Q_i-1,  durch Einfügen des Liniensegments s_i.     Was  ist  die  erwartete  Laufzeit  dieses  Algorithmus?  Wir  nehmen  an,  Schritt  1  kann  in  linearer
Zeit ausgeführt werden. Schritt 2 benötigt konstante Zeit. Für Schritt 3 betrachten wir die h, mit
1  =  h  =  log^* n.  Lemma  5  sagt  aus,  dass  der  Schritt  3.2  in  der  erwarteten  Zeit  O(n)  ausgeführt
werden kann. Wieviel  Zeit  brauchen wir für Schritt 3.1?  Die  erwarteten  Kosten  vom  Schritt 3.1.1
setzen sich aus den erwarteten Kosten um die Endpunkte von s_i zu lokalisieren und den erwarteten
Kosten für das ”threading” von s_i durch T_i-1 zusammen. Durch Lemma 2 wissen wir, dass Letzteres
konstante Kosten verursacht. Da die Endpunkte von s_i in T_N (h-1) schon lokalisiert sind, wissen wir
durch Lemma 4, dass die Lokalisierung in Erwartung nur O(log(i/N(h - 1))) Zeit benötigt. Da i = n
und N(h-1) = [n/ log^(h-1) n], liegt dieser Wert in O(log^(h) n). Für einen festen Wert von h wird der
Schritt 3.1.1 höchstens N(h) = [n/ log^(h) n] Mal ausgeführt. Zusammengefasst verursacht Schritt 3
lineare Kosten für einen festen Wert von h. Da Schritt 3 insgesamt log^* h mal ausgeführt wird, ergibt
sich die erwartete Laufzeit von O(n log^* n).     Schritt 4 läßt sich ähnlich wie Schritt 3.1 analysieren. Dabei sei zu beachten, dass N(log^* n) = n/e
und damit die erwarteten Lokalisierungskosten konstant sind. Folglich benötigt Schritt 4 in Erwartung
O(n) Zeit. Damit hätten wir folgendes bewiesen: Theorem 2  Sei S eine Menge von kreuzungsfreien Liniensegmenten in der Ebene, die eine einfache
polygonale Kette C  bilden.     Der oben beschriebene Algorithmus berechnet die Trapezzerlegung T (S) und die dazugehörige Such-
struktur Q(S) in der erwarteten Zeit O(n log^* n).     Die Suchstruktur benötigt in Erwartung  O(n) Platz und erledigt Suchanfragen in der erwarteten
Zeit O(log n).