2.2 Naiver Ansatz: SlowConvexHull

Idee

Direkte Umsetzung des Kantenkriteriums: Probiere jede mögliche gerichtete Kante $\vec{pq}$ aus und prüfe, ob irgendein anderer Punkt links davon liegt. Wenn nein, ist es eine Hüllkante.

Algorithmus (Folie 8)

 1  SortedList SlowConvexHull(PointSet P)
 2  {
 3      PointSet E = ∅;
 4      for all (geordnete Paare (p,q) ∈ P² mit p ≠ q) {
 5          valid = true;
 6          for all (Punkte r ∈ P \ {p,q}) {
 7              if (r liegt links der gerichteten Geraden pq)
 8                  valid = false;
 9          }
10          if (valid) füge die gerichtete Kante pq zu E hinzu;
11      }
12      SortedList L = ConstructSortedList(E);
13      return L;
14  }

Zeile für Zeile:

• Zeile 4: Geordnete Paare, d.h. $(p,q)$ und $(q,p)$ werden beide getestet. Das ist nötig, weil nur eine der beiden Richtungen im Uhrzeigersinn läuft.
• Zeilen 6–9: Teste alle übrigen Punkte mit dem Orientierungstest. Ein einziger Punkt links reicht, um die Kante zu verwerfen.
• Zeile 10: Überlebt die Kante, wird sie gemerkt.
• Zeile 12: $E$ enthält die Hüllkanten unsortiert. ConstructSortedList verkettet sie zu einem Polygon: Beginne mit einer Kante $\vec{pq}$, suche die Kante, die bei $q$ beginnt, usw.

Interaktiv durchspielen: Jeder Schritt testet eine gerichtete Kante. Rot schattiert ist die linke Seite – liegt dort ein Punkt (rot umkreist), fliegt die Kante raus. ⏩ springt zur nächsten gültigen Kante.

Schritt 1/31: p1→p2: kein Punkt links davon ⇒ Hüllkante, zu E hinzufügen.

langsamnormalschnellsehr schnell

Klicken: hinzufügen · Ziehen: verschieben · Rechtsklick: löschen · max. 10 Punkte

gültige Kanteungültige Kante / Punkt links davonErgebnis

Korrektheit

Der Algorithmus ist (fast) korrekt:

1. Rundungsfehler der Gleitkommaarithmetik werden vernachlässigt (Real-RAM-Modell).
2. Die Zeilen 3–11 liefern eine unsortierte Liste aller Kanten der konvexen Hülle.
3. Aber: Es gibt degenerierte Fälle!

Der degenerierte Fall: kollineare Punkte

Liegt ein Punkt $r$ genau auf der Geraden durch $p$ und $q$, ist $r$ weder links noch rechts.

Im Beispiel unten liegen drei Punkte auf der unteren Hüllkante. Spring mit ⏩ durch die gültigen Kanten: Akzeptiert wird nur die lange Kante, nicht die Teilstücke über den mittleren Punkt.

Schritt 1/21: p1→p2: kein Punkt links davon ⇒ Hüllkante, zu E hinzufügen.

langsamnormalschnellsehr schnell

Klicken: hinzufügen · Ziehen: verschieben · Rechtsklick: löschen · max. 10 Punkte

gültige Kanteungültige Kante / Punkt links davonErgebnis

Bei „links“ = $\operatorname{orient}>0$ (strikt) passiert Folgendes:

• $\vec{pr}$, $\vec{rq}$ und $\vec{pq}$ werden alle drei als gültig akzeptiert. $E$ enthält überlappende Kanten, und ConstructSortedList findet bei $p$ zwei Nachfolger.

Bei „links“ = $\operatorname{orient}\ge0$:

• Keine der drei Kanten wird akzeptiert, denn jeweils der dritte Punkt liegt „links“. Die Hülle hat ein Loch.

Korrekt ist: $\vec{pq}$ ist gültig, wenn alle anderen Punkte rechts liegen oder kollinear auf der Strecke $\overline{pq}$ (nicht dahinter oder davor). Dann ist nur $\vec{pq}$ gültig, und $r$ ist keine Ecke.

Solche Sonderfälle kommen bei Graham's Scan wieder und müssen dort genauso bedacht werden.

Laufzeit (Folie 10)

Zeile	Aufwand
4	$n^2-n = n(n-1)$ geordnete Paare
6	je $n-2$ Punkte
7	Orientierungstest: primitiv, $O(1)$
⇒ 3–11	$n(n-1)(n-2)\cdot O(1) = O(n^3)$
12	Verketten per Brute Force: für jede der $h\le n$ Kanten den Nachfolger unter allen Kanten suchen, also $O(n^2)$
Gesamt	$O(n^3)+O(n^2) = \mathbf{O(n^3)}$

Kann man das verbessern? Ja, deutlich. Der naive Ansatz verschwendet Arbeit: Er testet $\Theta(n^2)$ Kandidatenkanten, obwohl höchstens $n$ davon Hüllkanten sind. Die folgenden Algorithmen erzeugen Hüllkanten gezielter.