2.1 Definitionen

Konvexe Menge

Definition (konvexe Menge)

Eine Menge $S\subseteq\mathbb{R}^d$ heißt konvex, genau dann wenn für alle Punkte $p,q\in S$ die Verbindungsstrecke

$\overline{pq}=\{x : x=\lambda p+(1-\lambda)q,\ \lambda\in[0,1]\}$

in $S$ enthalten ist, also $\overline{pq}\subseteq S$.

In Worten: Man kann zwischen zwei beliebigen Punkten der Menge geradeaus laufen, ohne die Menge zu verlassen. Es gibt keine Dellen, Einbuchtungen oder Löcher.

Bei einer U-förmigen Menge dagegen kann man je einen Punkt $p$ und $q$ in die beiden „Arme“ legen. Die Strecke $\overline{pq}$ führt dann durch die Lücke dazwischen, also außerhalb der Menge. Die U-Form ist nicht konvex.

Zum Ausprobieren: Zieh $p$ und $q$ in die beiden Arme der U-Form, dann verlässt die Strecke die Menge. Bei der konvexen Form gelingt das nie.

p und q lassen sich ziehen.

Die Strecke p̄q verlässt S (rot) ⇒ S ist nicht konvex. Die konvexe Hülle füllt genau solche Einbuchtungen auf.

Beispiele: Kreisscheibe, Dreieck, Halbebene, Gerade und Strecke sind konvex. Ein Ring, ein „L“ oder ein Stern sind es nicht.

Wichtige Eigenschaft: Der Schnitt konvexer Mengen ist konvex. Liegen $p,q$ in allen Mengen, dann liegt $\overline{pq}$ auch in allen. Das braucht man für die nächste Definition.

Konvexe Hülle

Definition (konvexe Hülle)

Die konvexe Hülle $\mathcal{CH}(S)$ einer Menge $S\subseteq\mathbb{R}^d$ ist die kleinste konvexe Menge, die $S$ enthält, also der Schnitt aller konvexen Mengen, die $S$ enthalten.

Warum ist „Schnitt aller“ dasselbe wie „kleinste“? Der Schnitt ist nach der Eigenschaft oben konvex und enthält $S$. Und er ist in jeder konvexen Obermenge enthalten, also die kleinste.

Gummiband-Metapher

Man stellt sich die Punkte als Nägel in einem Brett vor, spannt ein Gummiband weit darum und lässt es los. Das Band zieht sich zusammen und legt sich an die äußersten Nägel. Seine Form ist die konvexe Hülle.

Das zeigt anschaulich:

• Die Hülle ist ein Polygon.
• Ihre Ecken sind Eingabepunkte, nämlich die Nägel, an denen das Band einen Knick macht.
• Innere Punkte und Punkte, die auf einer geraden Strecke des Bandes liegen, sind keine Ecken.

Das Gummiband zum Anfassen: Setze, verschiebe oder lösche Nägel. Die Hülle passt sich sofort an. Punkte innen oder mitten auf einer Kante (Preset „Kollinear“) sind keine Ecken.

Ersten und letzten Punkt der unteren Hülle entfernen (stehen schon oben). Ergebnis im Uhrzeigersinn: p1 → p2 → p8 → p10 → p9 → p5.

Klicken: hinzufügen · Ziehen: verschieben · Rechtsklick: löschen

Alternative Definition für $d=2$

Die konvexe Hülle $\mathcal{CH}(P)$ einer endlichen Menge $P$ von $n$ Punkten ist das eindeutige konvexe Polygon mit Ecken aus $P$, das alle Punkte von $P$ enthält.

Diese (informelle) Definition ist die Grundlage für die Algorithmen: Wir suchen eine Teilmenge der Eingabepunkte und ihre Reihenfolge auf dem Rand.

Problemstellung

• Eingabe: Eine Menge $P=\{p_1,p_2,\dots,p_n\}$ von $n$ paarweise verschiedenen Punkten in der Ebene.
• Ausgabe: Eine sortierte Liste von Punkten aus $P$ (laut Folie im Uhrzeigersinn), die die Ecken von $\mathcal{CH}(P)$ darstellt.

Die Reihenfolge gehört zur Ausgabe

Nur die Menge der Ecken auszugeben, wäre zu wenig: Um das Polygon zu zeichnen oder damit weiterzurechnen, braucht man die Reihenfolge entlang des Randes. Genau diese Ordnung macht das Problem mindestens so schwer wie Sortieren, siehe 2.3.

Beispiel der Folie: Eingabe $(p_1,\dots,p_8)$. Ausgegeben werden nur die 5 äußeren Punkte $p_2,p_4,p_5,p_7,p_8$ in Randreihenfolge. $p_1,p_3,p_6$ liegen innen.

Ein Kriterium für Hüllkanten

Die zentrale Beobachtung (Folie 7), auf der alle Algorithmen aufbauen:

Eine gerichtete Kante $\vec{pq}$ (mit $p,q\in P$) ist genau dann eine Kante der im Uhrzeigersinn orientierten Hülle, wenn kein anderer Punkt von $P$ links von ihr liegt.

Begründung: Läuft man im Uhrzeigersinn um ein konvexes Polygon, liegt das Innere immer rechts. Liegt also alles rechts von $\vec{pq}$ (oder darauf), ist die Gerade durch $p,q$ eine Stützgerade: Sie berührt die Punktmenge und hat sie ganz auf einer Seite. Mit dem Orientierungstest lässt sich „links von“ in $O(1)$ prüfen.

Algorithmenübersicht (Folie 6)

Prinzip	Algorithmen	Laufzeit
Inkrementell	naiv · Kallay	$O(n^3)$ · $O(n\log n)$
Rekursiv	Divide-and-Conquer · QuickHull	$O(n\log n)$
Sweeping	Graham, Andrew, TORCH	$O(n\log n)$
Output-sensitiv	Jarvis · Chan	$O(nh)$ · $O(n\log h)$, wenn $\mathcal{CH}(P)$ ein $h$-Eck ist

Anmerkung: QuickHull ist im Durchschnitt $O(n\log n)$, im Worst Case aber $O(n^2)$.

Output-sensitiv heißt: Die Laufzeit hängt nicht nur von der Eingabegröße $n$, sondern auch von der Ausgabegröße $h$ ab. Bei wenigen Hüllecken kann das deutlich schneller sein.