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

Lemma 3  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 seien T (S_i) und Q(S_i) die Trapezzerlegung und Suchstruktur für S_i,
die aus T (S_i-1) bzw. Q(S_i-1) durch Einfügen von s_i entstanden sind.     Sei  q  ein Punkt, den man in  T (S_n)  mittels  Q(S_n)  lokalisieren möchte. Unter Berüchsichtigung
aller Anordnungen von S  beträgt die erwartete Anzahl von Schlüsselvergleichen 5H_n O(log n). Beweis :  Sei t_j das Trapez in T (S_j), das q enthält. Angenommen t_i-1 ist bekannt, was ist dann E_i,
die erwartete Anzahl von Vergleichen um, t_i zu finden? Mit anderen Worten: Wir kennen das Trapez
aus T (S_i-1), das q  enthält. Was ist dann die erwartete Anzahl von Vergleichen, um das Trapez in
T (S_i) zu finden, welches q enthält?     Sind t_i-1  und t_i  gleich, dann sind keine Vergleiche nötig. Falls die Trapeze verschieden sind, ist
entweder eine der Seiten ein Teil des neuen Liniensegments s_i oder die horizontalen Erweiterungen
durch die Endpunkte von s_i.     Ist die rechte Seite von t_i ein Teil von s_i, ist exakt ein X-Vergleich zwischen q und s_i  nötig, um
t_i  zu identifizieren. zwischen q  und s_i. Wegen der zufälligen Anordnung ist die Wahrscheinlichkeit
dafür, dass s_i t_i von der rechten Seite eingrenzt, höchstens 1/i (t_i kann auch rechts unbegrenzt sein).
Folglich beträgt der Erwartungswert für die Anzahl der Vergleiche zwischen q und der rechten Seite
von t_i höchstens 1/i. Wegen der Symmetrie folgt das Gleiche für die linke Seite von t_i.     Falls die obere Seite von t_i  ein Teil der horizontalen Erweiterung durch einen Endpunkt von s_i
ist, ist ein zusätzlicher Vergleich nötig, nämlich ein  Y -Vergleich zwischen  q  und der horizontalen
Erweiterung. Wegen der zufälligen Reihenfolge der Liniensegmente tritt dieses Ereignis höchstens
mit der Wahrscheinlichkeit 1/i auf. Gleiches gilt für die Unterseite von t_i.     Die erwartete Anzahl von Vergleichen zwischen q und den Trapezseiten von t_i ist also höchstens
4/i. Mike Hohmeyer fand heraus, dass noch ein zusätzlicher Vergleich auftreten kann: Wir nehmen an,
dass die obere Seite von t_i, ein Teil der horizontalen Erweiterung durch den tiefergelegenen Endpunkt
von s_i  ist (was mit der Wahrscheinlichkeit 1/i auftreten kann). Weiterhin nehmen wir an, dass es
keine horizontale Erweiterung gibt, die s_i im Inneren schneidet, und dass kein anderes Liniensegment
aus S_i  einen gemeinsamen Endpunkt mit s_i  hat. Zusammengefasst bedeutet dies, dass s_i  komplett
in t_i-1 enthalten sein muß. Um q in t_i zu lokalisieren, muß zuerst ein Vergleich zwischen q und der
horizontalen Erweiterung des oberen Endpunktes stattfinden. Wenn also diese spezielle Konfiguration
auftaucht, ist ein weiterer Vergleich mit der Wahrscheinlichkeit von höchstens 1/i nötig.     Falls  wir  das  Trapez  t_i-i,  welches  q  enhielt  kennen,  müssen  wir  in  Erwartung  5/i  Vergleiche
anstellen, um das Trapez t_i zu finden, das nach Einfügen von s_i den Punkt q enthält. Es gilt deshalb
E_i = 5/i. Um das Lemma zu beweisen genügt es, die gesamte erwartete Anzahl von Vergleichen zu
betrachten ∑ _1=i=nE_i. ¤ Aus den Lemmata 2 und 3 und der davor geführten Diskussion folgt unmittelbar: Theorem 1  Sei  S  eine  Menge  von  n  kreuzungsfreien,  nicht-horizontalen  Liniensegmenten  in  der
Ebene. Seien T (S) die Trapezzerlegung  und Q(S) die Suchstruktur von S, die durch inkrementelles
Einfügen der Liniensegmente aus S  in zufälliger Reihenfolge entstanden sind. 1.  T (S) und Q(S) können in der erwarteten Zeit O(n log n) aufgebaut werden. 2.  Die erwartete Größe von Q(S) ist O(n). 3.  Für einen beliebigen Punkt q  brauchen wir in Erwartung  O(log n) Zeit, um q  in T (S) mittels Q(S) zu lokalisieren. (Die Erwartungswerte gelten hinsichtlich der zufälligen Anordnung der Liniensegmente aus S, wobei
jede Permutation von S  mit gleicher Wahrscheinlichkeit vorkommt.)