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

    Dieses Theorem lässt  sich  leicht  verallgemeinern.  Schließlich  setzt  der Algorithmus  nur eine Ei-
genschaft  voraus,  nämlich  dass  C  eine  Zusammenhangskomponente  repräsentiert.  Stellt  C  einen
verbundenen, planaren Graphen G dar, würde sich dieses Ergebnis weiterhin bestätigen. Schritt 3.2
müßte folglich modifiziert werden. In diesem Fall würden wir den kompletten Graphen durchlaufen,
indem  wir  einen  Algorithmus  zur  Graphdurchmusterung verwenden  würden. Wenn  wir  jetzt  noch
erlauben, dass  G  aus  mehreren Zusammenhangskomponenten  besteht,  lassen  sich  die  Theoreme 1
und 2 wie folgt vereinigen: Theorem 3  Sei S  eine Menge von kreuzungsfreien Liniensegmenten in der Ebene, die einen plana-
ren Graphen mit k Zusammenhangskomponenten repräsentiert. Weiterhin sei T (S) die Trapezzerle-
gung von S. •  Die Trapezzerlegung  T (S)  und die dazugehörige Suchstruktur  Q(S)  können in der Zeit O(n log^* n + k log n) aufgebaut werden. •  Die ewartete Größe von Q(S) ist O(n). •  Die erwartete Lokalisierungszeit für einen beliebigen Punkt q beträgt O(log n). Beweis :  Wir   benutzen   weiterhin   den   oben   beschriebenen   Algorithmus,   ändern   jedoch   den
Schritt 3.2  so  ab,  dass  die  Liniensegmente  jeder  Zusammenhangskomponente  des  Graphen  in  der
Reihenfolge  einer Graphdurchmusterung (z.B.  Tiefensuche) abgelaufen werden. Bei  diesem Schritt
werden  die  Zusammenhangskomponenten  nacheinander  abgearbeitet  und  die Endpunkte der  noch
nicht eingefügten Liniensegmente müssten dann noch lokalisiert werden. Lemma 3 sagt aus, dass die
Lokalisierungszeit für jede Zusammenhagskomponente in Erwartung O(log n) beträgt. ¤