Chans Algorithmus

Chans Algorithmus (englisch Chan’s algorithm) ist in der algorithmischen Geometrie ein ausgabesensitives Paradigma zur Berechnung der konvexen Hülle einer Menge von Punkten der Euklidischen Ebene oder des Raumes. Er kombiniert in einem Divide-and-conquer-Ansatz verschiedene bekannte Algorithmen, um eine asymptotisch optimale Laufzeit zu erzielen. Der Algorithmus ist benannt nach Timothy M. Chan, zeitgleich und unabhängig von ihm hat Frank Nielsen dieselbe Methode in seiner Dissertation entwickelt.

Problemstellung

Gegeben sei eine Menge $S\subset E^{2}$ von $n$ Punkten der Euklidischen Ebene, es ist die konvexe Hülle $\operatorname {conv} (S)$ zu berechnen. Hierbei wird die Hülle mit den Eckpunkten ihres Randes identifiziert, mit dieser Setzung gilt dann $\operatorname {conv} (S)\subseteq S$. Üblicherweise bezeichnet man die Mächtigkeit $|\operatorname {conv} (S)|$ der Hülle mit $h$, es ist also $h\leq n$. Für das Problem der konvexen Hülle sind verschiedene Lösungen bekannt, diese fallen stets in eine von zwei Kategorien: Bei den ausgabesensitiven Algorithmen beeinflusst sowohl die Eingabe- als auch die Ausgabegröße die Laufzeit; bei den nicht ausgabesensitiven Algorithmen hängt die Laufzeit dagegen ausschließlich von der Eingabegröße ab. Ein bekanntes Beispiel für eine ausgabesensitive Methode ist Jarvis’ March, die in Zeit $O(nh)$ läuft; der bekannteste nicht ausgabesensitive Algorithmus ist Graham’s Scan mit Laufzeit $O(n\log n)$ (siehe auch Landau-Notation).

Idealerweise würde man also gern für Instanzen mit kleiner Hülle eine ausgabesensitive Lösung wählen, während man für Eingaben mit vielen Punkten auf der Hülle eher einen nicht ausgabesensitiven Algorithmus bevorzugt. Allerdings ist die Größenordnung der Ausgabe üblicherweise unbekannt. Zusätzlich lässt sich im ausgabesensitiven Fall eine untere Laufzeitschranke beweisen, die mit $\Omega (n\log h)$ noch deutlich unter der Laufzeit von Jarvis’ March liegt. Chans Algorithmus gibt nun eine gemeinsame Methode für alle Eingaben an, die außerdem die optimale Laufzeit von $O(n\log h)$ erreicht.

Algorithmus

Die Funktionsweise von Chans Algorithmus beruht auf der folgenden Beobachtung: Soll per Jarvis’ March die konvexe Hülle einer Menge $P\subset E^{2}$ bestimmt werden, so wird stets ausgehend von einem bereits bekannten Punkt $p_{i}$ der konvexen Hülle ein weiterer Punkt $p_{i+1}\in P$ gesucht, so dass ganz $P$ links von der Strecke ${\overline {p_{i}\,p_{i+1}}}$ liegt. Normalerweise benötigt dies eine Rechenzeit in $O(|P|)$. Ist aber $\operatorname {conv} (P)$ bereits bekannt, reduziert sich der Aufwand durch binäre Suche auf $O(\log |P|)$. Die Definition von links bezieht sich dabei auf die Orientierung der Euklidischen Ebene und muss im dreidimensionalen Fall entsprechend angepasst werden.

Daraus ergibt sich folgende Berechnungsvorschrift:

Es sei eine natürliche Zahl $m\leq n$ gegeben.

1. Teile $S$ in (circa) $n/m$ Teilmengen $S_{j}$ mit jeweils höchstens $m$ Punkten auf.
2. Für jede der Mengen $S_{j}$ berechne $\operatorname {conv} (S_{j})$ via Graham’s Scan.
3. Setze die Teillösungen via Jarvis’ March wie folgt zusammen: Solange $i\leq m$ gilt,
   1. bestimme für den gerade aktuellen Punkt $s_{i}$ der konvexen Hülle und jede Teilmenge $S_{j}$ einen Kandidaten $s_{i+1,j}$, so dass $S_{j}$ vollständig links der Strecke ${\overline {s_{i}\,s_{i+1,j}}}$ liegt;
   2. bestimme aus den Kandidaten einen Punkt $s_{i+1}$, so dass die Menge $\{s_{i+1,j}\mid 1\leq j\leq n/m\}$ vollständig links der Strecke ${\overline {s_{i}\,s_{i+1}}}$ liegt.

Für $m\geq h$ erhält man durch diese Berechnung die gesamte konvexe Hülle der ursprünglichen Menge $S$, andernfalls bricht der Algorithmus zu früh ab. Entscheidend dabei ist, dass das Eintreten dieses Falles detektiert werden kann, ohne $h$ zu kennen. Die Berechnung in Schritt 3 kehrt nämlich nur dann zum fest gewählten Startpunkt $s_{1}$ zurück, wenn die gesamte Hülle gefunden wurde.

Es lässt sich nun eine vorläufige Laufzeitanalyse in Abhängigkeit von $m$ durchführen. Als nicht ausgabesensitiver Algorithmus benötigt Graham’s Scan im 2. Schritt für jedes der $S_{j}$ Zeit in $O(m\log m)$, insgesamt also $n/m\cdot O(m\log m)=O(n\log m)$. Da die konvexen Hüllen der Teilmengen bereits vorliegen, beschleunigt sich im Schritt 3.1 die Berechnung aller Kandidaten auf insgesamt $O((n/m)\log m)$. Schritt 3.2 benötigt sogar nur Zeit linear in $n/m$ und ist daher asymptotisch vernachlässigbar. Beide Teilschritte werden je $m$ Mal ausgeführt, es ergibt sich daher auch für den 3. Schritt eine Laufzeit in $O(n\log m)$. Insgesamt benötigt die Berechnung also Zeit $O(n\log m)$.

Könnte man nun einfach $m=h$ setzen, erhielte man einen optimalen Algorithmus, wie eingangs erwähnt ist die Größe der Ausgabe jedoch unbekannt. Diesem Problem kann man durch iterative Durchläufe mit immer größeren Werten für $m$ begegnen. Sobald das erste Mal $m\geq h$ gewählt wurde, kann die Berechnung beendet werden. Dabei ist die Geschwindigkeit der Erhöhung relevant für die Gesamtlaufzeit, man möchte weder zu viele Iterationen (durch zu langsames Erhöhen) noch zu lange Iterationen (durch zu schnelles Erhöhen). Chans Algorithmus beginnt dabei mit einem konstanten Wert für $m$ und quadriert diesen in jedem Durchlauf. Entsprechend werden nur (circa) $\log \log h$ viele Iterationen benötigt, bis $m$ die Größe der Ausgabe das erste Mal überschreitet. Für die finale Laufzeit ergibt sich nun

$\sum _{t=1}^{\log \log h}O(n\log 2^{2^{t}})=O(n)\cdot \sum _{t=1}^{\log \log h}O(2^{t})=O(n\cdot 2^{\log \log h})=O(n\log h)$,

wie gewünscht.