Konvexe Hülle
Die konvexe Hülle einer Teilmenge ist die kleinste konvexe Menge, die die Ausgangsmenge enthält. Betrachtet wird dieses Objekt in unterschiedlichen mathematischen Disziplinen wie zum Beispiel in der konvexen Analysis.

Definitionen 
Die konvexe Hülle einer Teilmenge  eines reellen oder komplexen Vektorraumes 

ist definiert als der Schnitt aller konvexen Obermengen von . Sie ist selbst konvex und damit die kleinste konvexe Menge, die  enthält. Die Bildung der konvexen Hülle ist ein Hüllenoperator.

Die konvexe Hülle kann auch beschrieben werden als die Menge aller endlichen Konvexkombinationen:

Der Abschluss der konvexen Hülle ist der Schnitt aller abgeschlossenen Halbräume, die  ganz enthalten. Die konvexe Hülle zweier Punkte  ist ihre Verbindungsstrecke:

Die konvexe Hülle endlich vieler Punkte ist ein konvexes Polytop.

Eine Menge von Punkten im euklidischen Raum ist konvex, wenn für je zwei beliebige Punkte, die zur Menge gehören, die Menge auch die Verbindungsstrecke enthält. Die konvexe Hülle einer Menge  kann wie folgt definiert werden:

 Die minimale konvexe Menge, die  als Teilmenge enthält
 Die Schnittmenge aller konvexen Mengen, die  als Teilmenge enthalten
 Die Menge aller Konvexkombinationen von Punkten in 
 Die Vereinigungsmenge aller Simplexe, deren Eckpunkte in  liegen
Es ist nicht offensichtlich, dass die erste Definition sinnvoll ist: Warum sollte es für jedes  eine eindeutige minimale konvexe Menge geben, die  enthält? Die zweite Definition, dieSchnittmenge aller konvexen Mengen, die  als Teilmenge enthalten, ist jedoch wohldefiniert. Sie ist eine Teilmenge jeder anderen konvexen Menge , die  enthält, weil  zu den Schnittmengen gehört. Es ist also genau die eindeutige minimale konvexe Menge, die  enthält. Daher sind die ersten zwei Definitionen äquivalent. Jede konvexe Menge, die  enthält, muss unter der Annahme, dass sie konvex ist, alle Konvexkombinationen von Punkten in  enthalten, so dass die Menge aller Konvexkombinationen in der Schnittmenge aller konvexen Mengen enthalten ist, die  enthalten. Umgekehrt ist die Menge aller Konvexkombinationen selbst eine konvexe Menge, die  enthält, also enthält sie auch die Schnittmenge aller konvexen Mengen, die  enthalten, und daher sind die zweite und dritte Definition äquivalent. Tatsächlich ist nach dem Satz von Carathéodory, wenn  eine Teilmenge eines -dimensionalen euklidischen Raums ist, jede Konvexkombination endlich vieler Punkte aus  auch eine Konvexkombination von höchstens  Punkten in . Die Menge von Konvexkombinationen eines -Tupels von Punkten ist ein Simplex. In der zweidimensionalen Ebene ist es ein Dreieck und im dreidimensionalen Raum ein Tetraeder. Daher gehört jede Konvexkombination von Punkten von  zu einem Simplex, dessen Ecken zu  gehören, und die dritte und vierte Definition sind äquivalent.

Beispiele 

 Das nebenstehende Bild zeigt die konvexe Hülle der Punkte (0,0), (0,1), (1,2), (2,2) und (4,0) in der Ebene. Sie besteht aus dem rot umrandeten Gebiet (inklusive Rand).

 Es gibt eine Klasse von Kurven (darunter z. B. die Bézierkurve), deren Mitglieder die sog. „Convex Hull Property“ (CHP) erfüllen, d. h. ihr Bild verläuft vollständig innerhalb der konvexen Hülle ihrer Kontrollpunkte.

Algorithmen 
Die Ermittlung der konvexen Hülle von  Punkten im  hat als untere Schranke eine asymptotische Laufzeit von ; der Beweis erfolgt durch Reduktion auf das Sortieren von  Zahlen. Liegen nur  der  Punkte auf dem Rand der konvexen Hülle, ist die Schranke bei .

Es bieten sich mehrere Algorithmen zur Berechnung an:
 Graham-Scan-Algorithmus mit Laufzeit 
 Jarvis-March (2d-Gift-Wrapping-Algorithmus) mit Laufzeit , wobei  die Anzahl der Punkte auf dem Rand der Hülle ist
 QuickHull in Anlehnung an Quicksort mit erwarteter Laufzeit ; Worst Case 
 Inkrementeller Algorithmus mit Laufzeit 
 Chans Algorithmus mit Laufzeit , wobei  die Anzahl der Punkte auf dem Rand der Hülle ist.

Weblinks 
 Allgemeines zu konvexen Hüllen samt Algorithmen zur Berechnung
 Java-Applet für Konvexe Hülle
 Zum randomisierten Algorithmus
 Java-Applet zur Demonstration der Berechnung der Konvexen Hülle einer gegebenen Punktmenge mit Hilfe der Algorithmen „Sweep“, „Jarvis March“ und „Graham Scan“
 Java-Applet zur interaktiven Durchführung des „Sweep“-Algorithmus
 Animation des Graham Scan Algorithmus
 Animation des Gift-Wrapping-Algorithmus
 Animation des QuickHull Algorithmus

Einzelnachweise 

Konvexe Hulle