Computational Geometry – Skript
Ausführliche Zusammenfassung der Vorlesung Computational Geometry (Prof. Dr. G. Umlauf, HTWG Konstanz, WS 2026/27), Kapitel für Kapitel entlang der Folien, aktuell bis Kapitel 5 (Voronoi & Delaunay), also alles für die Praktikumsaufgaben 1–4.
Schnell nachschlagen
- Suche: / oder Strg+K, Tippfehler sind egal.
- Spickzettel: alle Algorithmen, Laufzeiten, Formeln und ein Glossar DE/EN auf einer Seite.
- Mündliche Prüfung: Fragen mit Antworten zum Aufklappen und Tipps für die 40 Minuten.
| Kapitel | Folien | Worum es geht |
|---|---|---|
| Kapitel 0 – Einführung | 📄 00-intro.pdf | Organisation, Prüfung, Inhalte, Literatur |
| Kapitel 1 – Einführung & Grundlagen | 📄 01-basics.pdf | Typische Probleme, Punkte vs. Vektoren, primitive Operationen, Real RAM, Laufzeit, O-Kalkül, Master-Theorem |
| Kapitel 2 – Konvexe Hülle in 2D | 📄 02-hull.pdf | Konvexität, naiver Algorithmus, untere Schranke, Graham's Scan, Jarvis' March, Chan's Algorithmus |
| Kapitel 3 – Schnitt von Liniensegmenten | 📄 03-intersection.pdf | Sweep-Line-Prinzip, iso-orientierte Segmente, Bentley–Ottmann, AVL-Bäume & Heaps |
| Kapitel 4 – Bereichsanfragen | 📄 04-rangesearch.pdf | kd-Bäume, 1d-Bereichssuche, Range-Trees |
| Kapitel 5 – Voronoi & Delaunay | 📄 05-voronoi.pdf | Voronoi-Diagramme, Fortunes Algorithmus, Delaunay-Triangulierung, randomisierter Algorithmus |
So liest man das Skript
Jede Unterseite folgt einem Abschnitt der Folien (Nummerierung wie dort). Was auf den Folien nur als Stichpunkt oder „siehe Tafel“ steht, wird hier ausformuliert und mit Beispielen durchgerechnet. Ergänzungen, die nicht auf den Folien stehen, sind als solche markiert.
Praktikumsaufgaben
| # | Thema | Nachlesen |
|---|---|---|
| 1 | Graham's Scan + Jarvis' March | 2.4, 2.5 |
| 2 | Iso-orientierte Segmente | 3.3.1 |
| 3 | 2d-Bäume | 4.3 |
| 4 | Randomisierte Delaunay-Triangulierung | 5.4 |
Wie hängt das mit Abgabe 1 zusammen?
Aufgabe: Implementiere Graham's Algorithmus und Jarvis' Algorithmus zur Berechnung der konvexen Hülle von Punkten in der Ebene.
Was man dafür braucht:
- Den Orientierungstest (links / rechts / kollinear) → 1.2.2 Primitive Operationen
- Was die konvexe Hülle ist und in welcher Form sie ausgegeben wird → 2.1 Definitionen
- Graham's Scan → 2.4
- Jarvis' March → 2.5
- Für die Diskussion mit dem Professor: Laufzeiten, Sonderfälle, untere Schranke → 2.3