Im Folgenden zeigen wir, dass wenn S Liniensegmente enthält, die eine einfache polygonale Kette
bilden, können T (S) und Q(S) noch schneller aufgebaut werden.     Der kostenintensive Teil beim Einfügen eines Segments scheint die Lokalisierung der Endpunkte zu
sein. Falls nun S aus einer polygonalen Kette C besteht, kommt der Gedanke auf, die Liniensegmente
der Reihe nach entlang C  einzufügen. Beim Einfügen eines Liniensegments s_i  erspart man sich die
Lokalisierung des gemeinsamen Endpunktes von  s_i  und  s_i-1, der bereits beim Einfügen von  s_i-1
lokalisiert wurde. Die Position des anderen Endpunktes kann beim ”threading” ermittelt werden.
Leider verzichtet diese Strategie auf Randomisierung und man kann nicht mehr von konstanten
Kosten beim ”treading” ausgehen. Tatsächlich kann man schnell Beispiele finden, wo der ”threading”-
Vorgang O(i) Zeit für n/2 = i = n benötigt, was dann zu einem Algorithmus mit der Laufzeit O(n²)
führt.     Wir verfolgen die folgende Strategie: Die Liniensegmente werden weiterhin in zufälliger Reihenfolge
eingefügt. Gelegentlich halten wir aber an, um alle Endpunkte in der vorhandenen Trapezzerlegung
zu lokalisieren, indem wir uns entlang  C  bewegen. Um die EIzienz dieses Verfahrens zu zeigen,
brauchen wir zwei Lemmata. Das erste Lemma sagt uns, wie uns die gewonnen Informationen über
die zwischenzeitliche Lokalisierung der Endpunkte weiterhelfen, das andere hingegen gibt Auskunft
über die Kosten der Verfolgung von C durch die Trapezzerlegung. Lemma 4  Sei s₁, . . . , s_n eine zufällige Reihenfolge der Liniensegmente aus S, und S_i = {s₁, . . . , s_i}
mit 0 = i = n.     Sei 1 = j = k = n. Ist q  ein Punkt, dessen Position in T (S_j) bekannt ist, dann kann q mit Hilfe
von Q(S_k) in T (S_k) innerhalb der erwarteten Zeit 5(H_k - H_j) ε O(log(k/j)) lokalisiert werden. Beweis :  Wir verfahren wie im Beweis von Lemma 3. In diesem Fall beträgt die erwartete Lokali-
sierungszeit ∑ _j<i=kE_i. ¤ Lemma 5  Sei S eine Menge von kreuzungsfreien, nicht-horizontalen Liniensegmenten in der Ebene
und R eine beliebige Teilmenge von S der Größe r. Sei Z die erwartete Anzahl von Schnitten zwischen
den horizontalen Trapezseiten aus T (R) und den Liniensegmenten aus S\R.     Der Erwartungswert für Z  ist höchstens 4(n - r), wobei die Erwartung sich auf alle Untermengen
R von S mit |R| = r bezieht. Beweis :  Für T  ∝ S und s ε T bezeichne deg(s, T (T )) die Anzahl der horizontalen Erweiterungen in
T (T), die im Inneren von s enden. Da jede horizontale Erweiterung höchstens in zwei verschiedenen
Liniensegmenten endet, gilt ∑ sεT deg(s, T (T)) = 4|T|. Für  R     S  und  s  /                                     R  beträgt die Anzahl der horizontalen Trapezseiten in  T (R), die von  s
geschnitten werden, genau deg(s, T (R  {s}). Uns interessiert aber 1 __ ( n
r ) ∑   R∝S
|R|=r ∑ sεS\R deg(s, T (R  {s})). Setzen wir nun R ′ = R  {s}. Wenn wir die Doppelsumme etwas anders ausdrücken, erhalten wir 1 __ ( n
r ) ∑ R ′ S |R ∝ |=r+1 ∑ sεS ′ deg(s, T (R ′ )) = 1 __ ( n
r ) ∑ R ′ S |R ′ |=r+1 4|R ′ | = 4(r + 1) (   n
r+1
____ ) ( n
r ) = 4(n - r). ¤