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]

ProblemstellungBearbeiten

Gegeben sei eine Menge   von   Punkten der Euklidischen Ebene, es ist die konvexe Hülle   zu berechnen. Hierbei wird die Hülle mit den Eckpunkten ihres Randes identifiziert, mit dieser Setzung gilt dann  . Üblicherweise bezeichnet man die Mächtigkeit   der Hülle mit  , es ist also  . 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   läuft; der bekannteste nicht ausgabesensitive Algorithmus ist Graham’s Scan mit Laufzeit   (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   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   erreicht.

AlgorithmusBearbeiten

Die Funktionsweise von Chans Algorithmus beruht auf der folgenden Beobachtung: Soll per Jarvis’ March die konvexe Hülle einer Menge   bestimmt werden, so wird stets ausgehend von einem bereits bekannten Punkt   der konvexen Hülle ein weiterer Punkt   gesucht, so dass ganz   links von der Strecke   liegt. Normalerweise benötigt dies eine Rechenzeit in  . Ist aber   bereits bekannt, reduziert sich der Aufwand durch binäre Suche auf  . 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   gegeben.

  1. Teile   in (circa)   Teilmengen   mit jeweils höchstens   Punkten auf.
  2. Für jede der Mengen   berechne   via Graham's Scan.
  3. Setze die Teillösungen via Jarvis’ March wie folgt zusammen: Solange   gilt,
    1. bestimme für den gerade aktuellen Punkt   der konvexen Hülle und jede Teilmenge   einen Kandidaten  , so dass   vollständig links der Strecke   liegt;
    2. bestimme aus den Kandidaten einen Punkt  , so dass die Menge   vollständig links der Strecke   liegt.

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

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

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

 ,

wie gewünscht.

EinzelnachweiseBearbeiten

  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.