Betrachten wir den allgemeinen Fall, dass die Eingabe für den Algorithmus eine endliche, ungeordnete Menge von Punkten auf einer kartesischen Ebene ist. Ein wichtiger Spezialfall, bei dem die Punkte in der Reihenfolge der Durchquerung eines einfachen Polygons gegeben sind, wird später in einem separaten Unterabschnitt beschrieben.
Wenn nicht alle Punkte auf derselben Linie liegen, dann ist ihre konvexe Hülle ein konvexes Polygon, dessen Scheitelpunkte einige der Punkte der Eingabemenge sind. Die gebräuchlichste Darstellung ist eine Liste der Eckpunkte, die im oder gegen den Uhrzeigersinn entlang der Begrenzung angeordnet sind. In einigen Anwendungen ist es zweckmäßig, ein konvexes Polygon als Schnittpunkt einer Menge von Halbebenen darzustellen.
Untere Schranke für die RechenkomplexitätEdit
Für eine endliche Menge von Punkten in der Ebene ist die untere Schranke für die Rechenkomplexität des Auffindens der konvexen Hülle, die als konvexes Polygon dargestellt wird, leicht zu zeigen, dass sie dieselbe ist wie die für das Sortieren unter Verwendung der folgenden Reduktion. Für die Menge x 1 , … , x n {\displaystyle x_{1},\dots ,x_{n}}
Zahlen zu sortieren, betrachte die Menge der Punkte ( x 1 , x 1 2 ) , … , ( x n , x n 2 ) {\displaystyle (x_{1},x_{1}^{2}),\dots ,(x_{n},x_{n}^{2})}
von Punkten in der Ebene. Da sie auf einer Parabel liegen, die eine konvexe Kurve ist, ist es leicht zu sehen, dass die Scheitelpunkte der konvexen Hülle, wenn sie entlang des Randes durchlaufen werden, die sortierte Reihenfolge der Zahlen x 1 , … , x n {\displaystyle x_{1},\dots ,x_{n}}
. Es ist klar, dass für die beschriebene Umwandlung von Zahlen in Punkte und die anschließende Extraktion ihrer sortierten Reihenfolge lineare Zeit benötigt wird. Daher kann im allgemeinen Fall die konvexe Hülle von n Punkten nicht schneller berechnet werden als die Sortierung.
Die standardmäßige untere Schranke von Ω(n log n) für das Sortieren wird im Entscheidungsbaummodell des Rechnens bewiesen, in dem nur numerische Vergleiche, aber keine arithmetischen Operationen durchgeführt werden können; in diesem Modell können jedoch konvexe Hüllen überhaupt nicht berechnet werden. Auch im algebraischen Entscheidungsbaummodell, das für konvexe Hüllen besser geeignet ist, erfordert das Sortieren Ω(n log n) Zeit, und in diesem Modell benötigen konvexe Hüllen ebenfalls Ω(n log n) Zeit. In Modellen der Computerarithmetik, die es erlauben, Zahlen schneller als in O(n log n)-Zeit zu sortieren, z. B. durch die Verwendung ganzzahliger Sortieralgorithmen, können planare konvexe Hüllen jedoch auch schneller berechnet werden: der Graham-Scan-Algorithmus für konvexe Hüllen besteht aus einem einzigen Sortierschritt, gefolgt von einer linearen Menge zusätzlicher Arbeit.
Optimale ausgabesensitive AlgorithmenBearbeiten
Wie oben erwähnt, ist die Komplexität des Findens einer konvexen Hülle in Abhängigkeit von der Eingabegröße n durch Ω(n log n) nach unten begrenzt. Die Komplexität einiger Algorithmen für konvexe Hüllen kann jedoch sowohl in Abhängigkeit von der Eingabegröße n als auch von der Ausgabegröße h (der Anzahl der Punkte in der Hülle) charakterisiert werden. Solche Algorithmen werden als ausgabesensitive Algorithmen bezeichnet. Sie können asymptotisch effizienter als Θ(n log n)-Algorithmen sein, wenn h = o(n) ist.
Die untere Schranke für die Worst-Case-Laufzeit von ausgangssensitiven konvexen Hüllenalgorithmen wurde für den planaren Fall auf Ω(n log h) festgelegt. Es gibt mehrere Algorithmen, die diese optimale Zeitkomplexität erreichen. Der früheste Algorithmus wurde 1986 von Kirkpatrick und Seidel vorgestellt (sie nannten ihn den „ultimativen Konvexhüllen-Algorithmus“). Ein sehr viel einfacherer Algorithmus wurde 1996 von Chan entwickelt und wird Chans Algorithmus genannt.
AlgorithmenBearbeiten
Nachfolgend sind die bekannten Algorithmen für konvexe Hüllen aufgeführt, geordnet nach dem Datum der ersten Veröffentlichung. Die Zeitkomplexität jedes Algorithmus wird in Abhängigkeit von der Anzahl der Eingangspunkte n und der Anzahl der Punkte auf der Hülle h angegeben. Beachten Sie, dass im schlimmsten Fall h so groß wie n sein kann.
- Geschenkverpackung, auch bekannt als Jarvis-Marsch – O(nh)
Einer der einfachsten (wenn auch im schlimmsten Fall nicht der zeiteffizienteste) planaren Algorithmen. Unabhängig voneinander entwickelt von Chand & Kapur im Jahr 1970 und R. A. Jarvis im Jahr 1973. Er hat eine Zeitkomplexität von O(nh), wobei n die Anzahl der Punkte in der Menge und h die Anzahl der Punkte in der Hülle ist. Im schlimmsten Fall beträgt die Komplexität Θ(n2). - Graham scan – O(n log n)
Ein etwas anspruchsvollerer, aber viel effizienterer Algorithmus, der 1972 von Ronald Graham veröffentlicht wurde. Wenn die Punkte bereits nach einer der Koordinaten oder nach dem Winkel zu einem festen Vektor sortiert sind, dann benötigt der Algorithmus O(n) Zeit. - Quickhull
Unabhängig 1977 von W. Eddy und 1978 von A. Bykat entwickelt. Genau wie der Quicksort-Algorithmus hat er eine erwartete Zeitkomplexität von O(n log n), kann aber im schlimmsten Fall zu O(n2) entarten. - Divide and conquer – O(n log n)
Ein weiterer O(n log n)-Algorithmus, der 1977 von Preparata und Hong veröffentlicht wurde. Dieser Algorithmus ist auch auf den dreidimensionalen Fall anwendbar. - Monotone Kette, auch bekannt als Andrew’s Algorithmus- O(n log n)
Veröffentlicht 1979 von A. M. Andrew. Der Algorithmus kann als eine Variante des Graham-Scans betrachtet werden, bei dem die Punkte lexikografisch nach ihren Koordinaten sortiert werden. Wenn die Eingabe bereits sortiert ist, benötigt der Algorithmus O(n)-Zeit. - Inkrementeller konvexer Hüllenalgorithmus – O(n log n)
Veröffentlicht 1984 von Michael Kallay. - Kirkpatrick-Seidel-Algorithmus – O(n log h)
Der erste optimale ausgabeabhängige Algorithmus. Er modifiziert den Divide-and-Conquer-Algorithmus, indem er die Technik der Ehe-vor-Eroberung und der niedrigdimensionalen linearen Programmierung verwendet. Veröffentlicht von Kirkpatrick und Seidel im Jahr 1986. - Chans Algorithmus – O(n log h)
Ein einfacherer optimaler ausgangssensitiver Algorithmus, der 1996 von Chan entwickelt wurde. Er kombiniert das Einpacken von Geschenken mit der Ausführung eines O(n log n)-Algorithmus (z.B. Graham-Scan) auf kleinen Teilmengen der Eingabe.
Akl-Toussaint-HeuristikBearbeiten
Die folgende einfache Heuristik wird oft als erster Schritt bei der Implementierung von Algorithmen für konvexe Hüllen verwendet, um deren Leistung zu verbessern. Sie basiert auf dem effizienten Konvexhüllen-Algorithmus von Selim Akl und G. T. Toussaint, 1978. Die Idee besteht darin, schnell viele Punkte auszuschließen, die ohnehin nicht zur konvexen Hülle gehören würden. Diese Methode basiert auf der folgenden Idee. Finde die beiden Punkte mit den niedrigsten und höchsten x-Koordinaten und die beiden Punkte mit den niedrigsten und höchsten y-Koordinaten. (Jede dieser Operationen dauert O(n).) Diese vier Punkte bilden ein konvexes Viereck, und alle Punkte, die in diesem Viereck liegen (mit Ausnahme der vier anfänglich gewählten Scheitelpunkte), sind nicht Teil der konvexen Hülle. Die Suche nach all diesen Punkten, die in diesem Viereck liegen, ist ebenfalls O(n), und somit ist die gesamte Operation O(n). Optional können auch die Punkte mit den kleinsten und größten Summen der x- und y-Koordinaten sowie die Punkte mit den kleinsten und größten Differenzen der x- und y-Koordinaten zum Viereck hinzugefügt werden, so dass ein unregelmäßiges konvexes Achteck entsteht, dessen Innenseiten sicher verworfen werden können. Wenn es sich bei den Punkten um Zufallsvariablen handelt, dann führt dieser wegwerfbare Vorverarbeitungsschritt für eine kleine, aber häufig vorkommende Klasse von Wahrscheinlichkeitsdichtefunktionen dazu, dass ein Konvexhüllen-Algorithmus in linearer erwarteter Zeit läuft, selbst wenn die Komplexität des Konvexhüllen-Algorithmus im schlimmsten Fall quadratisch in n ist.
Online- und dynamische Konvexhüllen-ProblemeEdit
Die obige Diskussion betrachtet den Fall, dass alle Eingabepunkte im Voraus bekannt sind. Man kann zwei weitere Fälle betrachten.
- Online-Konvexhüllenproblem: Die Eingabepunkte werden nacheinander erhalten. Nachdem jeder Punkt am Eingang angekommen ist, muss die konvexe Hülle für die bis dahin erhaltene Punktmenge effizient berechnet werden.
- Dynamische Konvexhüllenpflege: Die Eingabepunkte können sequentiell eingefügt oder gelöscht werden, und die konvexe Hülle muss nach jeder Einfüge-/Löschoperation aktualisiert werden.
Das Einfügen eines Punktes kann die Anzahl der Scheitelpunkte einer konvexen Hülle höchstens um 1 erhöhen, während das Löschen eine konvexe Hülle mit n Scheitelpunkten in eine Hülle mit n-1 Scheitelpunkten umwandeln kann.
Die Online-Version kann mit O(log n) pro Punkt behandelt werden, was asymptotisch optimal ist. Die dynamische Version kann mit O(log2 n) pro Operation behandelt werden.
Einfaches PolygonBearbeiten
Die konvexe Hülle eines einfachen Polygons wird durch das Polygon in Teile geteilt, von denen einer das Polygon selbst ist und die übrigen Taschen sind, die durch ein Stück des Polygonrands und eine einzelne Hüllenkante begrenzt werden. Obwohl viele Algorithmen für das Problem der Konstruktion der konvexen Hülle eines einfachen Polygons veröffentlicht wurden, ist fast die Hälfte von ihnen falsch.McCallum und Avis lieferten den ersten korrekten Algorithmus.Eine spätere Vereinfachung von Graham & Yao (1983) und Lee (1983) verwendet nur eine einzige Stack-Datenstruktur. Ihr Algorithmus durchläuft das Polygon im Uhrzeigersinn, beginnend mit dem äußersten linken Eckpunkt. Dabei speichert er eine konvexe Folge von Scheitelpunkten auf dem Stapel, die noch nicht als innerhalb von Taschen liegend identifiziert worden sind. Bei jedem Schritt folgt der Algorithmus einem Pfad entlang des Polygons von der Spitze des Stapels bis zum nächsten Scheitelpunkt, der sich nicht in einer der beiden Taschen neben der Spitze des Stapels befindet. Solange sich die beiden obersten Scheitelpunkte des Stapels und der neue Scheitelpunkt nicht in einer konvexen Position befinden, wird der Stapel geleert, bevor der neue Scheitelpunkt auf den Stapel geschoben wird. Wenn die Traversierung im Uhrzeigersinn den Ausgangspunkt erreicht, gibt der Algorithmus die Folge der Stapelscheitelpunkte als Hülle zurück.