2.4 Graham's Scan

Geschichte

• 1972 von Ronald L. Graham entwickelt.
• 1979 von A. M. Andrew verbessert.

Die Folien zeigen die Variante nach Andrew (Monotone Chain): Sortierung nach $x$-Koordinate, getrennte obere und untere Hülle. Grahams Original sortiert stattdessen nach dem Winkel um einen Startpunkt. Andrews Version kommt ohne Winkel aus und behandelt Sonderfälle einfacher.

Grundidee: inkrementell, von links nach rechts

Graham's Scan ist ein inkrementeller Algorithmus:

• Die Punkte werden einzeln betrachtet und nacheinander zur Lösung hinzugefügt.
• Das passiert von links nach rechts.
• Dafür werden die Punkte nach ihrer $x$-Koordinate sortiert.

Problem: Die Ecken der Hülle sollen in Randreihenfolge entstehen. Läuft man von links nach rechts, kommen aber oben und unten liegende Ecken durcheinander.

Lösung (Folie 14): Berechne zuerst die obere Hülle, dann die untere Hülle.

• Getrennt wird an den Punkten mit minimaler und maximaler $x$-Koordinate, $p_1$ und $p_n$ nach dem Sortieren. Beide gehören sicher zur Hülle, denn ganz links und ganz rechts kann nichts mehr kommen.
• Obere Hülle: der Randteil von $p_1$ über oben nach $p_n$.
• Untere Hülle: der Randteil von $p_n$ über unten zurück nach $p_1$.

Im Bild unten sind $p_1$ und $p_n$ der linkeste und der rechteste Punkt. Dort zerfällt die Hülle in die obere Hülle (violett) und die untere Hülle (blau). Setz ruhig eigene Punkte.

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

Die Schlüsselbeobachtung: nur Rechtskurven

Läuft man die obere Hülle von links nach rechts ab, biegt man an jeder Ecke nach rechts ab, im Uhrzeigersinn um das Innere herum.

Daraus folgt die Regel: Bilden die letzten drei Punkte $a,b,c$ der aktuellen Kette keine Rechtskurve, dann liegt $b$ unterhalb der Strecke $\overline{ac}$ (oder auf ihr). $b$ kann dann keine Ecke der oberen Hülle sein und wird gelöscht. Danach prüft man erneut die nun letzten drei Punkte, denn auch der Punkt vor $b$ könnte jetzt überflüssig sein.

Für die untere Hülle gilt dasselbe, gespiegelt: Von rechts nach links abgelaufen, sind auch dort nur Rechtskurven erlaubt. Deshalb ist der Code für beide Hälften identisch, nur die Laufrichtung ist umgekehrt.

Der Rechtskurven-Test (Folie 17)

Drei Punkte $(p,w,q)$ haben eine Rechtskurve, wenn $w$ links der Strecke $\overline{pq}$ liegt.

Mit dem Orientierungstest:

$a\to b\to c \text{ ist Rechtskurve} \iff \operatorname{orient}(a,b,c) < 0.$

(Beide Formulierungen sind gleichwertig: $c$ rechts von $\vec{ab}$ ⇔ $b$ links von $\vec{ac}$.)

Algorithmus (Folie 15)

 1  Polygon GrahamScan(Points P) {
 2      Sortiere Punkte nach x-Koordinate (p1,...,pn);
 3      Lupper.append(p1); Lupper.append(p2);
 4      for (i = 3; i <= n; i++) {
 5          Lupper.append(pi);
 6          while (Lupper enthält mehr als zwei Punkte und
 7                 die letzten drei Punkte a,b,c machen eine Linkskurve)
 8              Lupper.delete(b);
 9      }
10      Llower.append(pn); Llower.append(pn-1);
11      for (i = n-2; i >= 1; i--) {
12          Llower.append(pi);
13          while (Llower enthält mehr als zwei Punkte und
14                 die letzten drei Punkte a,b,c machen eine Linkskurve)
15              Llower.delete(b);
16      }
17      Llower.delete(ersten Punkt); Llower.delete(letzten Punkt);
18      return Lupper.append(Llower);
19  }

Zeile für Zeile:

Zeile	Bedeutung
2	Sortieren – sorgt dafür, dass jeder neue Punkt der bisher rechteste ist
3	Die obere Kette startet mit den zwei linkesten Punkten
5	Neuer Punkt $p_i$ wird immer angehängt, er ist der rechteste bisher und damit sicher Ecke der Hülle der bisherigen Punkte
6–8	Solange die letzten drei eine Linkskurve bilden: mittleren Punkt entfernen. Die Liste verhält sich wie ein Stack
10–16	dasselbe für die untere Hülle, von rechts nach links
17	Der erste Punkt von $L_\text{lower}$ ist $p_n$, der letzte $p_1$. Beide stehen schon in $L_\text{upper}$ und werden entfernt, damit sie nicht doppelt vorkommen
18	Obere + untere Hülle = alle Ecken im Uhrzeigersinn, beginnend bei $p_1$

Interaktiv durchspielen: Setze eigene Punkte und gehe den Algorithmus Schritt für Schritt durch. Violett ist die obere Kette, blau die untere, das Dreieck zeigt den Test der letzten drei Punkte. ⏩ springt zum nächsten neuen Punkt.

Schritt 1/49: Punkte lexikographisch sortiert: p1, p2, p3, p4, p5, p6, p7, p8, p9, p10 (erst nach x, bei Gleichstand nach y).

langsamnormalschnellsehr schnell

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

obere Hülleuntere HülleRechtskurve: okkeine Rechtskurve: löschen

Durchgerechnetes Beispiel

Punkte (bereits lexikographisch sortiert): $A(0,0)$, $B(1,2)$, $C(2,1)$, $D(3,3)$, $E(4,0)$.

Obere Hülle (links → rechts):

Schritt	Liste nach Anhängen	Test der letzten drei	Aktion	Liste danach
Start	A B	–	–	A B
+C	A B C	orient(A,B,C) $=1\cdot1-2\cdot2=-3$: Rechtskurve	–	A B C
+D	A B C D	orient(B,C,D) $=1\cdot1-(-1)\cdot2=3$: Linkskurve	C löschen	A B D
	A B D	orient(A,B,D) $=1\cdot3-2\cdot3=-3$: Rechtskurve	–	A B D
+E	A B D E	orient(B,D,E) $=2\cdot(-2)-1\cdot3=-7$: Rechtskurve	–	A B D E

Untere Hülle (rechts → links, Reihenfolge E, D, C, B, A):

Schritt	Liste	Test	Aktion	danach
Start	E D	–	–	E D
+C	E D C	orient(E,D,C) $=(-1)(1)-(3)(-2)=5$: Linkskurve	D löschen	E C
+B	E C B	orient(E,C,B) $=(-2)(2)-(1)(-3)=-1$: Rechtskurve	–	E C B
+A	E C B A	orient(C,B,A) $=(-1)(-1)-(1)(-2)=3$: Linkskurve	B löschen	E C A
	E C A	orient(E,C,A) $=(-2)(0)-(1)(-4)=4$: Linkskurve	C löschen	E A

Zeile 17: E und A entfernen, $L_\text{lower}$ ist leer.

Ergebnis: A → B → D → E (im Uhrzeigersinn). C liegt innen. Die untere Kante $\overline{EA}$ schließt das Polygon. ✔

Dasselbe Beispiel zum Nachklicken (um $(5,2)$ verschoben, die orient-Werte bleiben gleich):

Schritt 1/19: Punkte lexikographisch sortiert: A, B, C, D, E (erst nach x, bei Gleichstand nach y).

langsamnormalschnellsehr schnell

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

obere Hülleuntere HülleRechtskurve: okkeine Rechtskurve: löschen

Laufzeit (Folie 16)

Satz 2

Die konvexe Hülle von $n$ Punkten in der Ebene kann in $O(n\log n)$ berechnet werden.

Teil	Aufwand
Lexikographisches Sortieren	$O(n\log n)$
Obere Hülle, for-Schleife (Zeile 4)	$n-2$ Durchläufe
Obere Hülle, while-Schleife (Zeile 6)	insgesamt höchstens $n$ Löschungen
⇒ obere Hülle	$O(n)$
Untere Hülle	analog $O(n)$
Gesamt	$O(n\log n)$

Warum ist die while-Schleife insgesamt nur $O(n)$?

Auf den ersten Blick sieht es nach $O(n^2)$ aus: eine while-Schleife in einer for-Schleife, und die while-Schleife kann in einem Schritt viele Punkte löschen.

Amortisierte Argumentation: Jeder Punkt wird genau einmal angehängt und höchstens einmal gelöscht, denn gelöschte Punkte kommen nie zurück. Jeder while-Durchlauf, dessen Test zutrifft, löscht einen Punkt. Also gibt es über den gesamten Algorithmus höchstens $n$ erfolgreiche Tests. Dazu kommt pro for-Durchlauf ein Test, der fehlschlägt und die Schleife beendet. Zusammen sind das höchstens $2n$ Tests, also $O(n)$.

Das Sortieren dominiert. Sind die Punkte schon sortiert, läuft der Scan in $O(n)$.

Mit der unteren Schranke folgt: Graham's Scan ist worst-case-optimal.

Korrektheit (Folie 16)

Beweis durch Induktion über die Anzahl der verarbeiteten Punkte.

Invariante: Nach Verarbeitung von $p_1,\dots,p_i$ enthält $L_\text{upper}$ genau die Ecken der oberen Hülle von $\{p_1,\dots,p_i\}$, von links nach rechts.

• Anfang ($i=2$): $p_1,p_2$ ist trivialerweise die obere Hülle zweier Punkte.
• Schritt $i\to i+1$: $p_{i+1}$ ist der rechteste Punkt und daher sicher eine Ecke der neuen oberen Hülle. Ecken der alten Hülle, die jetzt unter der neuen Kante zu $p_{i+1}$ liegen, sind keine Ecken mehr. Das sind genau die Punkte am Ende der Liste, an denen beim Anhängen von $p_{i+1}$ eine Linkskurve entsteht. Die while-Schleife entfernt sie von hinten. Sobald eine Rechtskurve entsteht, ist die restliche Kette nach Induktionsvoraussetzung schon konvex und bleibt unverändert.

Untere Hülle analog.

Sonderfälle (Folie 18)

„Der Algorithmus ist nicht korrekt!“

1. Mehrere Punkte mit gleicher $x$-Koordinate

Dann ist die Ordnung „nach $x$ sortiert“ nicht eindeutig. Liegen z.B. zwei Punkte senkrecht übereinander ganz links, ist nicht klar, welcher $p_1$ ist, und der Scan kann je nach Reihenfolge falsch abbiegen.

Lösung: lexikographisch sortieren. Bei gleicher $x$-Koordinate entscheidet die $y$-Koordinate:

$p < q \iff p_x<q_x \ \lor\ (p_x=q_x \land p_y<q_y).$

Das entspricht einer infinitesimal kleinen Drehung des Koordinatensystems: Jetzt haben alle Punkte verschiedene „$x$-Werte“.

2. Drei Punkte im Rechtskurven-Test liegen auf einer Geraden

Ist $\operatorname{orient}(a,b,c)=0$, macht der Weg $a\to b\to c$ weder eine Links- noch eine Rechtskurve. Die Folie sagt: „Keine Rechtskurve!“ Also wird $b$ gelöscht. Der Punkt liegt auf der Kante $\overline{ac}$ und ist keine echte Ecke.

Daraus folgt: Die Löschbedingung ist nicht „Linkskurve“ ($\operatorname{orient}>0$), sondern „keine Rechtskurve“, also $\operatorname{orient}(a,b,c)\ge0$.

Weitere Fälle (Ergänzung)

Fall	Verhalten
$n\le 2$	Es gibt kein Polygon. Die Punkte direkt zurückgeben
Doppelte Punkte	Die Problemstellung verlangt paarweise verschiedene Punkte. In der Praxis Duplikate nach dem Sortieren entfernen
Alle Punkte kollinear	Obere Hülle wird $[p_1,p_n]$, untere $[p_n,p_1]$. Nach Zeile 17 bleibt $[p_1,p_n]$, eine Strecke. Funktioniert ohne Sonderbehandlung

In C++ (Ergänzung)

Umsetzung von Folie 15 mit den Sonderfällen

struct PointF { double x, y; };

// > 0: Linkskurve, < 0: Rechtskurve, == 0: kollinear
double orient(const PointF& a, const PointF& b, const PointF& c)
{
    return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
}

bool lexLess(const PointF& a, const PointF& b)
{
    return a.x < b.x || (a.x == b.x && a.y < b.y);
}

bool samePoint(const PointF& a, const PointF& b)
{
    return a.x == b.x && a.y == b.y;
}

std::vector<PointF> grahamScan(std::vector<PointF> P)
{
    std::sort(P.begin(), P.end(), lexLess);                          // Zeile 2, lexikographisch
    P.erase(std::unique(P.begin(), P.end(), samePoint), P.end());    // Duplikate entfernen
    const int n = int(P.size());
    if (n < 3) return P;

    std::vector<PointF> upper{P[0], P[1]};                           // Zeile 3
    for (int i = 2; i < n; ++i) {                                    // Zeile 4
        upper.push_back(P[i]);
        while (upper.size() > 2 &&                                   // "keine Rechtskurve"
               orient(upper[upper.size() - 3], upper[upper.size() - 2], upper.back()) >= 0)
            upper.erase(upper.end() - 2);                            // b löschen
    }

    std::vector<PointF> lower{P[n - 1], P[n - 2]};                   // Zeile 10
    for (int i = n - 3; i >= 0; --i) {                               // Zeile 11
        lower.push_back(P[i]);
        while (lower.size() > 2 &&
               orient(lower[lower.size() - 3], lower[lower.size() - 2], lower.back()) >= 0)
            lower.erase(lower.end() - 2);
    }

    upper.insert(upper.end(), lower.begin() + 1, lower.end() - 1);   // Zeilen 17–18
    return upper;                                                    // im Uhrzeigersinn
}