2.6 Chan's Algorithmus

Die Frage

Welche Komplexität haben output-sensitive Algorithmen für die konvexe Hülle?

• Untere Schranke: $\Omega(n\log h)$ [Kirkpatrick & Seidel, 1986]. Kirkpatrick und Seidel haben selbst einen Algorithmus mit $O(n\log h)$ angegeben („The ultimate planar convex hull algorithm?“), der aber kompliziert ist.
• Einfach erreicht wird die Schranke durch Chan's Algorithmus (Timothy Chan, 1995/96), auch Nielsens Algorithmus genannt (Frank Nielsen hat ihn unabhängig gefunden). Er ist eine Kombination aus Graham's Scan und Jarvis' March.
• Optimierungen stammen von Emo Welzl.

Idee

Jarvis ist langsam, weil jeder Wrapping-Schritt alle $n$ Punkte anschaut. Chan beschleunigt diesen Schritt:

1. Vorverarbeitung mit Graham: Teile die $n$ Punkte in $k=n/m$ Gruppen zu je höchstens $m$ Punkten und berechne für jede Gruppe die Hülle mit Graham. Kosten: $O(\tfrac{n}{m}\cdot m\log m)=O(n\log m)$.
2. Wrapping mit Jarvis über die Gruppenhüllen: Statt alle $n$ Punkte zu prüfen, sucht man in jeder Gruppenhülle den besten Kandidaten. Da diese konvex und sortiert ist, geht das per binärer Suche in $O(\log m)$. Pro Wrapping-Schritt kostet das also $O(\tfrac{n}{m}\log m)$ statt $O(n)$.
3. Problem: Man kennt $h$ nicht, also weiß man nicht, wie man $m$ wählen soll. Lösung: $h$ raten und die Schätzung schnell steigern.

Algorithmus (Folie 23)

 1  Polygon ChansAlgorithm(Points P)
 2  {
 3      for (t = 1, 2, ... bis Hülle gefunden) {
 4          H = min(2^(2^t), n);           // Schätzung für die Eckenzahl h
 5          Partitioniere P in k = n/m Teilmengen P1,...,Pk der Größe ≤ m;
 6          Berechne CH(P1),...,CH(Pk) mit Graham's Scan;
 7          Finde lexikographisch kleinsten Punkt p1; p0 = (−∞, 0);
 8          for (j = 1, ..., H) {           // versuche eine Hülle mit ≤ H Ecken
 9              for (i = 1, ..., k)         // Wrapping von CH(P1),...,CH(Pk)
10                  Berechne qi ∈ CH(Pi)\{pj}, das den Winkel ∢ p(j-1) pj qi maximiert,
                    mit "binärer Suche" auf CH(Pi);
11              p(j+1) = der Punkt aus {q1,...,qk}, der ∢ p(j-1) pj q maximiert;
12              if (p(j+1) == p1) return Hülle gefunden;
13          }   // H zu klein, keine Hülle mit H Ecken gefunden
14      }       // Schätzung für h verbessern
15  }

Struktur (Folie 24):

Zeilen	Teil
3–4	Iteration, um die unbekannte Eckenzahl $h$ zu finden
5–6	Vorverarbeitung: Graham's Scan auf den Gruppen
7–13	Jarvis' March über die Gruppenhüllen, abgebrochen nach $H$ Schritten

Erläuterungen:

• Mit $m=H$ ist die Gruppengröße gleich der geschätzten Eckenzahl.
• $p_0=(-\infty,0)$ ist ein Hilfspunkt, damit der erste Winkel (wie bei Jarvis zur Horizontalen) dieselbe Formel benutzt.
• Ist nach $H$ Schritten die Hülle nicht geschlossen, war die Schätzung zu klein. Man bricht ab und startet mit größerem $H$ neu. Dadurch kostet eine Runde nie mehr als $H$ Wrapping-Schritte.

Interaktiv durchspielen: Die Farben sind die Gruppen, jede mit ihrer Teilhülle. In jedem Wrapping-Schritt sucht man in jeder Gruppe den besten Kandidaten (gestrichelt) und nimmt davon den besten (Pfeil). Reicht $H$ nicht, wird die Runde rot abgebrochen und $H$ quadriert.

Schritt 1/18: Runde t = 1: H = m = min(2^(2^1), n) = 4. Zerlege in k = ⌈40/4⌉ = 10 Gruppen und berechne deren Hüllen mit Graham.

langsamnormalschnellsehr schnell

n = 40t = 1, H = m = 4, k = 10 Gruppen

Laufzeit einer Runde (Folie 25)

Zeile	Teil	Aufwand
5	Partitionieren	$O(n)$
6	Hüllen der Gruppen	$O\big(\tfrac{n}{m}\cdot m\log m\big)$
7	Wrapping initialisieren	$O(n)$
8	Iterationen	$O(H)$
9	Iterationen	$O(n/m)$
10	Wrapping jeder Hülle (binäre Suche)	$O(\log m)$
11	Wrapping der Hüllen (bestes $q_i$)	$O(n/m)$

Zusammen für Zeilen 4–13:

$$O\Big(n + n\log m + n + H\big(\tfrac{n}{m}\log m + \tfrac{n}{m}\big)\Big) = O\Big(n\log m + H\,\tfrac{n}{m}\log m\Big).$$

Wahl von $m$ und $H$ (Folie 26)

1. Mit $m=H$ wird eine Runde zu $O(n\log H + n\log H) = O(n\log H)$.

Die Zeilen 3–4 laufen, bis $H\ge h$ ist (oder schlimmstenfalls $H=n$):

$h\le H=2^{2^t}\iff \log_2 h\le 2^t\iff \log_2\log_2 h\le t.$

Gesamtlaufzeit über alle Runden:

$$\sum_{t=1}^{\lceil\log\log h\rceil} O\big(n\log 2^{2^t}\big) = O\Big(n\sum_{t=1}^{\lceil\log\log h\rceil} 2^t\Big) = O\big(n\cdot 2^{\log\log h}\big) = O(n\log h).$$

Warum $2^{2^t}$ (Quadrieren) statt $2^t$ (Verdoppeln)? Eine Runde kostet $O(n\log H)$. Beim Quadrieren verdoppelt sich $\log H$ von Runde zu Runde ($2^t$). Die Kosten bilden eine geometrische Reihe, die von der letzten Runde dominiert wird, und die kostet $O(n\log h)$. Beim Verdoppeln von $H$ würde $\log H$ nur um 1 wachsen, man hätte $\log h$ Runden à bis zu $n\log h$, insgesamt $O(n\log^2 h)$.

2. Heuristisch besser in Zeile 4: $H=\min\big(2^{t^2},\,n\big)$, das wächst weniger aggressiv.

3. Gute Balance zwischen $m$ und $H$: $m=\min(H\log H,\ n)$.

4. In Zeile 10 kann man lineare Suche statt binärer Suche nehmen („Hülle der Hüllen“). Das ist einfacher zu implementieren und ändert die Gesamtlaufzeit nicht [Welzl], denn die Laufzeit für das Wrapping ist ohnehin kleiner.

Einordnung

Algorithmus	Laufzeit	$h$ klein	$h=n$
Graham	$O(n\log n)$	$n\log n$	$n\log n$
Jarvis	$O(nh)$	$\approx n$	$n^2$
Chan	$O(n\log h)$	$\approx n$	$n\log n$

Chan ist immer mindestens so gut wie der bessere der beiden und erreicht die untere Schranke $\Omega(n\log h)$. Er ist also optimal output-sensitiv.