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

Wir wollen mit dem unteren Endpunkt b ähnlich verfahren und die Trapezzerlegung T ″ sowie die Suchstruktur Q ″ aus T ′ bzw. Q ′                                                 ableiten.
Nun ”fädeln”¹  wir das Liniensegment s durch T ″ , indem wir alle Trapeze bestimmen, die von s durchschnitten werden. Diese Trapeze werden in zweigeteilt und auf jeder Seite verschmelzen wir die
horizontalen Erweiterungen aus T ″ mit s. So erhalten wir T (S ′ ). Die Suchstruktur Q(S ′ ) erhalten wir wie folgt: Für jedes neue Trapez aus T (S ′ ) erzeugen wir die entsprechende Senke in der Suchstruktur. Jede Senke aus  Q ″                                                                                                   , die von  s  zerschnitten wurde, wird
zu einem X-Knoten mit dem Schlüssel s und den zwei neuerzeugten Senken als Kinderknoten. Das
Trapez aus T ″ , das b enthält, bekommt noch einen Y -Knoten, da es zusätzlich durch die horizontale Erweiterung, die durch b verläuft, geteilt wird. Die Zeit, die wir benötigen um T (S ′ ) und Q(S ′                                                                                 ) aus T (S) bzw. Q(S) abzuleiten, setzt sich aus
der Zeit für die Lokalisirung der beiden Endpunkte und der ”threading”-Zeit zusammen. Letzteres
ist proportional zur der Anzahl der horizontalen Erweiterungen aus T (S), die s schneiden, oder der
Anzahl der horizontalen Erweiterungen aus T (S ′ ), die in s münden.     Wieviel Zeit brauchen wir um  T (S) zu erzeugen, wenn wir die Liniensegmente nacheinander
einfügen, beginnend mit leeren Strukturen? O.ensichtlich ist dies abhängig von der Einfügereihen-
folge. Zwar ist  T (S) von dieser Reihenfolge unabhängig,  Q(S) und die Zeit um einen Punkt zu
lokalisieren, hängen aber sehr stark von dieser Reihenfolge ab. Schlechte Beispiele sind schnell gefun-
den: Stellen wir uns eine Menge S vor, mit n vertikalen Liniensegmenten, die die x-Achse schneiden.
Werden die Liniensegmente nach der steigenden x-Koordinate eingefügt, dann werden die Pfade von
der Wurzel zur Senke in Q(S) lang. Wollen wir nun einen Punkt lokalisieren, der auf der x-Achse
liegt und sich rechts von allen Liniensegmenten befindet, dann benötigen wir O(n) Zeit.     Künftig argumentieren wir, dass wenn die Liniensegmente in zufälliger Reihenfolge eingefügt wer-
den, wobei jede Anordnung mit gleicher Wahrscheinlichkeit vorkommt, verhält sich Q(S) in Erwar-
tung besser. Dadurch wird die erwartete Zeit für die Konstruktion der Strukturen auch angemessen,
die sich bekanntlich aus der erwarteten Zeit für die Lokalisierung der Punkte und der erwarteten
”threading”-Zeit zusammensetzt. Die folgenden Lemmata geben Auskunft über diese Zeiten. Lemma 2  Sei s₁, . . . , s_n eine zufällige Reihenfolge der Liniensegmente aus S, und S_i = {s₁, . . . , s_i}
mit 0 = i = n. Für 1 < i = n ist die erwartete Anzahl der horizontalen Erweiterungen aus T (S_i-1),
die von s_i geschnitten werden, höchstens 4. Beweis :  Für ein Liniensegment s ε S bezeichne deg(s, T (S_i)) die Anzahl der horizontalen Erweite-
rungen aus T (S_i), die im Inneren von s enden. Als nächtes betrachten wir die Anzahl der horizonta-
len Erweiterungen, die in s_i enden. Da dieser Wert in T (S_i-1) und T (S_i) gleich ist, interessiert uns
Exp(deg(s_i, T (S_i))).
Da T (S_i) höchstens 2i horizontale Erweiterungen hat und jede Erweiterung in höchstens zwei Lini-
ensegmenten endet, folgt ∑ sεS                                                _ideg(s, T (S_i)) = 4i. Weil wir eine zufällige Reihenfolge der Linienseg-
mente angenommen haben, ist s_i irgendein Segment aus S_i mit gleicher Wahrscheinlichkeit. Daraus
folgt unmittelbar Exp(deg(s_i, T (S_i))) = 4. ¤     Sei H_n = 1 + 1/2 + 1/3 + . . . + 1/n. Wir bemerken, dass H_n = T(log n). Genauer gilt für n > 1,
log n < H_n < 1 + log n. ¹threading  ist der Fachausdruck für diese Prozedur.