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

1   Einführung Die Triangulation von Polygonen findet in vielen Bereichen Anwendung, deshalb war die Berechen-
barkeit dieses Problems schon früher von großer Bedeutung. Trotzdem blieb diese Berechenbarkeit
bis vor einem Jahrzehnt ungelöst. Das Problem kann wie folgt näher spezifiziert werden: Problem: Gegeben seien die Koordinaten von n aufeinander folgenden Ecken eines einfachen Poly-
gons P . Gesucht werden n - 3 Diagonalen, die P  in n - 2 Dreiecke teilen. Eine kurze Geschichte: 1978  verö.entlichte  Garey  ein Verfahren mit der Komplexität  O(n log n),
welches auf einem Sweep basierte. Vier Jahre später präsentierte Chazelle einen Algorithmus mit
gleicher Komplexität. Die O(n log n) Grenze wurde dann von O(n log C_P ) unterboten, wobei C_P  den
”shape” Parameter beschreibt, der nicht größer als n ist und vom Polygon P  abhängt.
Tarjan und Van Wyk machten 1986 einen Durchbruch mit einem O(n log log n) Algorithmus. Drei
Jahre  später  erreichte  auch  ein  einfacheres  Verfahren  von  Kirkpatrick  diese  Zeitschranke.  Zwi-
schenzeitlich präsentierte Clarkson einen randomisierten Algorithmus mit der erwarteten Laufzeit
O(log^* n).  Schließlich  entdeckte  Chazelle  ein  deterministisches  Verfahren  mit  linearer  Laufzeit,
welches die Frage der Komplexität dieses Problems beantwortete.
Diese Ausarbeitung stellt einen randomisierten Algorithmus mit der erwarteten Laufzeit O(n log^* n)
vor. Die Tugend des Verfahrens liegt in der Einfachheit. Außerdem ist dieser Algorithmus praktisch
und  läßt  sich  leicht  implementieren,  was  man  von  den  meisten  o.g.  Algorithmen  nicht  behaupten
kann.  Wie  die  meisten  Vorgänger,  kann  unserer  Algorithmus  ein  Polygon  P  nicht  direkt  triangu-
lieren.  Zunächst  wird  eine  Struktur  berechnet,  die  als  ”Trapezzerlegung”  von  P  bezeichnet  wird.
Fournier und Montuno stellten  fest,  dass  sich  die  Triangulation  von P  aus  dieser  Struktur  in
linearer Zeit ableiten läßt.