Konvexe Hülle

Die konvexe Hülle e​iner Teilmenge i​st die kleinste konvexe Menge, d​ie die Ausgangsmenge enthält. Betrachtet w​ird dieses Objekt i​n unterschiedlichen mathematischen Disziplinen w​ie zum Beispiel i​n der konvexen Analysis.

Die blaue Menge ist die konvexe Hülle der roten Menge

Definitionen

Die konvexe Hülle einer Teilmenge ${\displaystyle X}$ eines reellen oder komplexen Vektorraumes ${\displaystyle V}$

${\displaystyle \operatorname {conv} X:=\bigcap _{X\subseteq K\subseteq V \atop K\ \mathrm {konvex} }K}$

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

Die konvexe Hülle k​ann auch beschrieben werden a​ls die Menge a​ller endlichen Konvexkombinationen:[1]

${\displaystyle \operatorname {conv} X=\left\{\left.\sum _{i=1}^{n}{\alpha _{i}\cdot x_{i}}\right|x_{i}\in X,n\in \mathbb {N} ,\sum _{i=1}^{n}\alpha _{i}=1,{\alpha _{i}}\geq 0\right\}}$

Der Abschluss der konvexen Hülle ist der Schnitt aller abgeschlossenen Halbräume, die ${\displaystyle X}$ ganz enthalten. Die konvexe Hülle zweier Punkte ${\displaystyle a,b}$ ist ihre Verbindungsstrecke:

${\displaystyle \operatorname {conv} \{a,b\}={\overline {ab}}:=\{\lambda a+(1-\lambda )b\mid 0\leq \lambda \leq 1\}}$

Die konvexe Hülle endlich vieler Punkte i​st 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 ${\displaystyle X}$ kann wie folgt definiert werden:

1. Die minimale konvexe Menge, die ${\displaystyle X}$ als Teilmenge enthält
2. Die Schnittmenge aller konvexen Mengen, die ${\displaystyle X}$ als Teilmenge enthalten
3. Die Menge aller Konvexkombinationen von Punkten in ${\displaystyle X}$
4. Die Vereinigungsmenge aller Simplexe, deren Eckpunkte in ${\displaystyle X}$ liegen

Es ist nicht offensichtlich, dass die erste Definition sinnvoll ist: Warum sollte es für jedes ${\displaystyle X}$ eine eindeutige minimale konvexe Menge geben, die ${\displaystyle X}$ enthält? Die zweite Definition, dieSchnittmenge aller konvexen Mengen, die ${\displaystyle X}$ als Teilmenge enthalten, ist jedoch wohldefiniert. Sie ist eine Teilmenge jeder anderen konvexen Menge ${\displaystyle Y}$, die ${\displaystyle X}$ enthält, weil ${\displaystyle Y}$ zu den Schnittmengen gehört. Es ist also genau die eindeutige minimale konvexe Menge, die ${\displaystyle X}$ enthält. Daher sind die ersten zwei Definitionen äquivalent. Jede konvexe Menge, die ${\displaystyle X}$ enthält, muss unter der Annahme, dass sie konvex ist, alle Konvexkombinationen von Punkten in ${\displaystyle X}$ enthalten, so dass die Menge aller Konvexkombinationen in der Schnittmenge aller konvexen Mengen enthalten ist, die ${\displaystyle X}$ enthalten. Umgekehrt ist die Menge aller Konvexkombinationen selbst eine konvexe Menge, die ${\displaystyle X}$ enthält, also enthält sie auch die Schnittmenge aller konvexen Mengen, die ${\displaystyle X}$ enthalten, und daher sind die zweite und dritte Definition äquivalent. Tatsächlich ist nach dem Satz von Carathéodory, wenn ${\displaystyle X}$ eine Teilmenge eines ${\displaystyle d}$-dimensionalen euklidischen Raums ist, jede Konvexkombination endlich vieler Punkte aus ${\displaystyle X}$ auch eine Konvexkombination von höchstens ${\displaystyle d+1}$ Punkten in ${\displaystyle X}$. Die Menge von Konvexkombinationen eines ${\displaystyle (d+1)}$-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 ${\displaystyle X}$ zu einem Simplex, dessen Ecken zu ${\displaystyle X}$ gehören, und die dritte und vierte Definition sind äquivalent.

Beispiele

Konvexe Hülle der rot markierten Punkte im zweidimensionalen Raum

• 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 ${\displaystyle n}$ Punkten im ${\displaystyle \mathbb {R} ^{2}}$ hat als untere Schranke eine asymptotische Laufzeit von ${\displaystyle \Omega (n\log n)}$; der Beweis erfolgt durch Reduktion auf das Sortieren von ${\displaystyle n}$ Zahlen. Liegen nur ${\displaystyle k}$ der ${\displaystyle n}$ Punkte auf dem Rand der konvexen Hülle, ist die Schranke bei ${\displaystyle \Omega (n\log k)}$.

Es bieten s​ich mehrere Algorithmen z​ur Berechnung an[2][3]:

• Graham-Scan-Algorithmus mit Laufzeit ${\displaystyle {\mathcal {O}}(n\log n)}$
• Jarvis-March (2d-Gift-Wrapping-Algorithmus) mit Laufzeit ${\displaystyle {\mathcal {O}}(nk)}$, wobei ${\displaystyle k}$ die Anzahl der Punkte auf dem Rand der Hülle ist
• QuickHull in Anlehnung an Quicksort mit erwarteter Laufzeit ${\displaystyle {\mathcal {O}}(n\log n)}$; Worst Case ${\displaystyle {\mathcal {O}}(n^{2})}$
• Inkrementeller Algorithmus mit Laufzeit ${\displaystyle {\mathcal {O}}(n\log n)}$
• Chans Algorithmus mit Laufzeit ${\displaystyle {\mathcal {O}}(n\log k)}$, wobei ${\displaystyle k}$ die Anzahl der Punkte auf dem Rand der Hülle ist.

• 
  Animation des Graham Scan Algorithmus
• 
  Animation des Gift-Wrapping-Algorithmus. Die rote Linien zeigen die bereits gefundenen Strecken der konvexen Hülle, die schwarze zeigt die aktuell Beste, und die grüne Linie zeigt die Strecke, die gerade überprüft wird.
• 
  Animation des QuickHull Algorithmus

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

1. Wolfram MathWorld: Convex Hull
2. Franco P. Preparata and Michael Ian Shamos: Computational Geometry - An Introduction. Springer-Verlag, 1985, 1st edition: ISBN 0-387-96131-3; 2nd printing, corrected and expanded, 1988: ISBN 3-540-96131-3; Russian translation, 1989: ISBN 5-03-001041-6.
3. GitHub, Inc.: Convex Hull Algorithms