Konvexe Hülle

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

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 X eines reellen oder komplexen Vektorraumes V

$\operatorname{conv} X := \bigcap_{X\subseteq K \subseteq V \atop K\ \mathrm{konvex}} K$

ist definiert als der Schnitt aller konvexen Obermengen. Sie ist selbst konvex und damit die kleinste konvexe Menge, die X 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:

$\operatorname{conv} X = \left\{\left. \sum_{i=1}^{n}{\alpha_{i} \cdot x_{i}} \right| x_i \in X, n\in\mathbb{N}, \sum^n_{i=1} \alpha_i = 1 ,{\alpha_{i}} \ge 0 \right\}$

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

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

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

Beispiele

Konvexe Hülle einer endlichen Anzahl von Punkten 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.

Berechnung im zweidimensionalen Fall

Die Ermittlung der konvexen Hülle von n Punkten im $\mathbb R^2$ hat als untere Schranke Ω(nlog n); der Beweis erfolgt durch Reduktion auf das Sortieren von n Zahlen. Liegen nur k der n Punkte auf dem Rand der konvexen Hülle, ist die Schranke bei Ω(nlog k).

Es bieten sich mehrere Algorithmen zur Berechnung an^[1]:

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

Weblinks

• Allgemeines zu konvexen Hüllen samt Algorithmen zur Berechnung
• Applet zur Berechnung und Visualisierung der konvexen Hülle, Delaunay-Triangulation und des Voronoi-Diagramms im Raum
• Java Applet für Konvexe Hülle
• Zum randomisierten Algorithmus (engl., PDF, 81 kB)
• Java Applet zur Demonstration der Berechnung der Konvexen Hülle einer gegebenen Punktmenge mit Hilfe der Algorithmen "Sweep", "Jarvis March" und "Graham Scan"

Literatur

1. ↑ 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