Konvexe Hülle - LinkFang.de





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 [math]X[/math] eines reellen oder komplexen Vektorraumes [math]V[/math]

[math]\operatorname{conv} X := \bigcap_{X\subseteq K \subseteq V \atop K\ \mathrm{konvex}} K[/math]

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

[math]\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\}[/math]

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

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

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

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.

Berechnung im zweidimensionalen Fall

Die Ermittlung der konvexen Hülle von [math]n[/math] Punkten im [math]\mathbb R^2[/math] hat als untere Schranke eine asymptotische Laufzeit von [math]\Omega(n \log n)[/math]; der Beweis erfolgt durch Reduktion auf das Sortieren von [math]n[/math] Zahlen. Liegen nur [math]k[/math] der [math]n[/math] Punkte auf dem Rand der konvexen Hülle, ist die Schranke bei [math]\Omega(n \log k)[/math].

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

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

Weblinks

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.

Kategorien: Keine Kategorien vorhanden!

Quelle: Wikipedia - http://de.wikipedia.org/wiki/Konvexe Hülle (Vollständige Liste der Autoren des Textes [Versionsgeschichte])    Lizenz: CC-by-sa-3.0

Änderungen: Alle Bilder mit den meisten Bildunterschriften wurden entfernt. Ebenso alle zu nicht-existierenden Artikeln/Kategorien gehenden internen Wikipedia-Links (Bsp. Portal-Links, Redlinks, Bearbeiten-Links). Entfernung von Navigationsframes, Geo & Normdaten, Mediadateien, gesprochene Versionen, z.T. ID&Class-Namen, Style von Div-Containern, Metadaten, Vorlagen, wie lesenwerte Artikel. Ansonsten sind keine Inhaltsänderungen vorgenommen worden. Weiterhin kann es durch die maschinelle Bearbeitung des Inhalts zu Fehlern gerade in der Darstellung kommen. Darum würden wir jeden Besucher unserer Seite darum bitten uns diese Fehler über den Support mittels einer Nachricht mit Link zu melden. Vielen Dank!

Stand der Informationen: August 201& - Wichtiger Hinweis: Da die Inhalte maschinell von Wikipedia übernommen wurden, ist eine manuelle Überprüfung nicht möglich. Somit garantiert LinkFang.de nicht die Richtigkeit und Aktualität der übernommenen Inhalte. Sollten die Informationen mittlerweile fehlerhaft sein, bitten wir Sie darum uns per Support oder E-Mail zu kontaktieren. Wir werden uns dann innerhalb von spätestens 10 Tagen um Ihr Anliegen kümmern. Auch ohne Anliegen erfolgt mindestens alle drei Monate ein Update der gesamten Inhalte.