🟦 Konvexe Hülle

In der 2D-Spielephysik ist die konvexe Hülle eines Polygons seine minimale konvexe Umhüllung. Zwei konvexe Polygone können mit dem Trennungsachsentheorem (SAT) auf Überschneidung geprüft werden: Existiert eine trennende Linie, überlappen sie sich nicht. Der GJK-Algorithmus erweitert dies auf 3D und behandelt gekrümmte Objekte über die Minkowski-Differenz.

Punkte, die auf einer Hüllenkante liegen, aber keine Eckpunkte sind, können je nach Algorithmusvariante ein- oder ausgeschlossen werden. Der Standard-Graham-Scan schließt kollineare innere Punkte aus und liefert die minimale Eckpunktmenge. Manche Anwendungen bevorzugen den Einschluss aller Randpunkte.

Chans Algorithmus (Timothy Chan, 1996) erreicht O(n log h) Zeit, wobei h die Anzahl der Hüllenpunkte ist — dies ist optimal, weil die Ausgabe von h Punkten Ω(h) Zeit und das Sortieren von n Punkten Ω(n log n) Zeit benötigt. Chans Ansatz schätzt h in Verdopplungsphasen und führt einen Mini-Jarvis-March aus, der nach h Schritten stoppt.

In der 2D-linearen Optimierung ist der durch m Ungleichheitsbedingungen definierte zulässige Bereich ein konvexes Polygon — eine konvexe Hülle der Schnittpunkte der Bedingungen. Die optimale Lösung eines linearen Programms liegt immer an einem Eckpunkt des zulässigen Polytops. Die Simplex-Methode durchläuft Eckpunkte dieses Polytops.

In 3D ist die konvexe Hülle von n Punkten ein konvexes Polyeder mit höchstens O(n) Ecken, Kanten und Flächen. Algorithmen umfassen den 3D-Graham-Scan, Divide-and-Conquer (O(n log n)) und die Gift-Wrapping-Variante. Der QuickHull3D-Algorithmus von Barber, Dobkin und Huhdanpaa (1996, qhull-Bibliothek) ist der praktische Standard, verwendet u. a. in SciPy und MATLAB.

Doppelte Punkte (identische Koordinaten) müssen explizit behandelt werden; die meisten Implementierungen entfernen Duplikate vor dem Ausführen des Hüllenalgorithmus. Beim Graham Scan würden doppelte Punkte zu Kreuzprodukten von null führen, was die Winkelsortierung mehrdeutig macht.

Es gibt eine klassische Dualität: Das 2D-Voronoi-Diagramm von n Punkten entspricht der Projektion der 3D-konvexen Hülle derselben, auf das Paraboloid z = x² + y² angehobenen Punkte. Die untere Hülle projiziert zurück auf die Delaunay-Triangulierung, deren dualer Graph das Voronoi-Diagramm ist.

Bei Support-Vector-Machines (SVMs) entspricht der Maximum-Margin-Klassifikator zwischen zwei Punktklassen dem Finden der nächstgelegenen Punkte auf den konvexen Hüllen beider Klassen. Die Support-Vektoren der SVM sind genau die der trennenden Hyperebene nächstgelegenen Hüllenpunkte.

Graham Scan läuft in O(n log n) durch die anfängliche Winkelsortierung. Jarvis March (Gift Wrapping) läuft in O(nh), wobei h die Anzahl der Hüllenpunkte ist: im schlimmsten Fall O(n²). Quickhull hat durchschnittlich O(n log n), im schlimmsten Fall O(n²). Chans Algorithmus (1996) erreicht in allen Fällen das optimale O(n log h).

Für drei Punkte A, B, C berechnet man das 2D-Kreuzprodukt (B − A) × (C − A). Ein positiver Wert bedeutet, dass C links von der gerichteten Linie A→B liegt (Gegenuhrzeigersinn), ein negativer Wert rechts (im Uhrzeigersinn), und null bedeutet kollinear. Dieser O(1)-Orientierungstest ist die grundlegende Operation in allen Algorithmen für konvexe Hüllen.

Das Problem der konvexen Hülle hat eine Ω(n log n) untere Schranke im algebraischen Entscheidungsbaummodell, bewiesen durch eine Reduktion vom Sortieren: Platziert man n Zahlen als Punkte (xᵢ, xᵢ²) auf einer Parabel, ist ihre konvexe Hülle die gesamte Menge, in sortierter Reihenfolge zurückgegeben.