Kapitel 2 – Konvexe Hülle in 2D

Folien: 📄 02-hull.pdf · Praktikumsaufgabe 1

„Konvexe-Hülle-Algorithmen sind für die algorithmische Geometrie, was Sortieren für diskrete Algorithmen ist.“ (Folie 5, frei übersetzt)

Die konvexe Hülle ist das Einstiegsproblem der algorithmischen Geometrie. An ihr sieht man fast alle Grundtechniken des Fachs:

• inkrementelle Konstruktion und Sweep (Graham)
• output-sensitive Algorithmen (Jarvis, Chan)
• untere Schranken durch Reduktion (Sortieren → Hülle)
• Degenerierte Fälle (kollineare Punkte, gleiche Koordinaten) und Rundungsfehler

Aufbau

Abschnitt	Inhalt	Laufzeit
2.1 Definitionen	konvexe Menge, konvexe Hülle, Problemstellung, Algorithmenübersicht	–
2.2 Naiver Ansatz	SlowConvexHull: alle Kanten testen	$O(n^3)$
2.3 Untere Schranke	Reduktion Sortieren → Hülle	$\Omega(n\log n)$
2.4 Graham's Scan	Sortieren + obere/untere Hülle	$O(n\log n)$
2.5 Jarvis' March	Gift Wrapping	$O(n\cdot h)$
2.6 Chan's Algorithmus	Graham + Jarvis kombiniert	$O(n\log h)$

$n$ = Anzahl der Eingabepunkte, $h$ = Anzahl der Ecken der Hülle (Ausgabegröße).