Chans Algorithmus

Chans Algorithmus (engl.: 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[1], zeitgleich und unabhängig von ihm hat Frank Nielsen dieselbe Methode in seiner Dissertation entwickelt.[2][3]

Problemstellung

Gegeben sei eine Menge ${\displaystyle S\subset E^{2}}$ von ${\displaystyle n}$ Punkten der Euklidischen Ebene, es ist die konvexe Hülle ${\displaystyle \operatorname {conv} (S)}$ zu berechnen. Hierbei wird die Hülle mit den Eckpunkten ihres Randes identifiziert, mit dieser Setzung gilt dann ${\displaystyle \operatorname {conv} (S)\subseteq S}$. Üblicherweise bezeichnet man die Mächtigkeit ${\displaystyle |\operatorname {conv} (S)|}$ der Hülle mit ${\displaystyle h}$, es ist also ${\displaystyle 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 ${\displaystyle O(nh)}$ läuft; der bekannteste nicht ausgabesensitive Algorithmus ist Graham’s Scan mit Laufzeit ${\displaystyle 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 ${\displaystyle \Omega (n\log h)}$ noch deutlich unter der Laufzeit von Jarvis’ March liegt.[4] Chans Algorithmus gibt nun eine gemeinsame Methode für alle Eingaben an, die außerdem die optimale Laufzeit von ${\displaystyle 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 ${\displaystyle P\subset E^{2}}$ bestimmt werden, so wird stets ausgehend von einem bereits bekannten Punkt ${\displaystyle p_{i}}$ der konvexen Hülle ein weiterer Punkt ${\displaystyle p_{i+1}\in P}$ gesucht, so dass ganz ${\displaystyle P}$ links von der Strecke ${\displaystyle {\overline {p_{i}\,p_{i+1}}}}$ liegt. Normalerweise benötigt dies eine Rechenzeit in ${\displaystyle O(|P|)}$. Ist aber ${\displaystyle \operatorname {conv} (P)}$ bereits bekannt, reduziert sich der Aufwand durch binäre Suche auf ${\displaystyle 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 s​ich folgende Berechnungsvorschrift:

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

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

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

Es lässt sich nun eine vorläufige Laufzeitanalyse in Abhängigkeit von ${\displaystyle m}$ durchführen. Als nicht ausgabesensitiver Algorithmus benötigt Graham's Scan im 2. Schritt für jedes der ${\displaystyle S_{j}}$ Zeit in ${\displaystyle O(m\log m)}$, insgesamt also ${\displaystyle 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 ${\displaystyle O((n/m)\log m)}$. Schritt 3.2 benötigt sogar nur Zeit linear in ${\displaystyle n/m}$ und ist daher asymptotisch vernachlässigbar. Beide Teilschritte werden je ${\displaystyle m}$ Mal ausgeführt, es ergibt sich daher auch für den 3. Schritt eine Laufzeit in ${\displaystyle O(n\log m)}$. Insgesamt benötigt die Berechnung also Zeit ${\displaystyle O(n\log m)}$.

Könnte man nun einfach ${\displaystyle 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 ${\displaystyle m}$ begegnen. Sobald das erste Mal ${\displaystyle 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 ${\displaystyle m}$ und quadriert diesen in jedem Durchlauf. Entsprechend werden nur (circa) ${\displaystyle \log \log h}$ viele Iterationen benötigt, bis ${\displaystyle m}$ die Größe der Ausgabe das erste Mal überschreitet. Für die finale Laufzeit ergibt sich nun

${\displaystyle \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.

Einzelnachweise

1. T. M. Chan: Optimal output-sensitive convex hull algorithms in two and three dimensions. In: Discrete & Computational Geometry. 16, Nr. 4, 1996, S. 361–368.
2. F. Nielsen: Algorithmes géométriques adaptatifs. Dissertation (franz.), Université de Nice Sophia-Antipolis, 1996.
3. F. Nielsen: Grouping and Querying: A Paradigm to Get Output-Sensitive Algorithms. In: Discrete and Computational Geometry Japanese Conference (JCDCG'98). Revised Papers. (= Lecture Notes in Computer Science). Band 1763. Springer, Berlin, Heidelberg 2000, S. 250–257.
4. D. Kirkpatrick, R. Seidel: The Ultimate Planar Convex Hull Algorithm?. In: SIAM J. Comput.. 15, Nr. 1, 1983, S. 287–299.