Algorithmische Geometrie
Dozent: Thomas Bläsius
Übungsleiter: Marcus Wilhelm
In der Vorlesung Algorithmische Geometrie beschäftigen wir uns mit dem Entwurf und der Analyse geometrischer Algorithmen und Datenstrukturen.
Prüfung
Es gibt zwei Prüfungstermine: Donnerstag 24.2. (alle Termine bereits vergeben) und Mittwoch 23.3.
Zur Anmeldung bitte eine E-Mail mit Wunschtermin ans Sekretariat (scale.info@iti.uka.de) schreiben und im Campus Management System anmelden.
Weihnachtsvorlesung (TGI)
Im Rahmen der Diesjährigen TGI Vorlesung wird es eine Weihnachtsvorlesung mit dem Titel Magic: The Gathering is Turing Complete geben. Sie wird am Donnerstag (23.12.) um 12 Uhr im Fritz-Haller-HS (HS 37, 20.40) stattfinden. Bitte beachtet die Hinweise zu den Corona-Beschränkungen auf der TGI Homepage.
Termine
| Montag (18 Uhr) | Freitag (12 Uhr) | ||
|---|---|---|---|
| 22.10. | Vorlesung | ||
| 25.10. | Aktiv-Session | 29.10 | Vorlesung |
| | Übung | 5.11. | Vorlesung |
| 8.11. | Aktiv-Session | 12.11. | Vorlesung |
| 15.11. | Übung | 19.11. | Vorlesung |
| 22.11. | Aktiv-Session | 26.11. | Vorlesung |
| 29.11. | Übung | 3.12. | Vorlesung |
| 6.12. | Aktiv-Session | 10.12. | Vorlesung |
| 13.12. | Übung | 17.12. | Vorlesung |
| 20.12. | Aktiv Session | — | |
| — | — | ||
| — | 7.1. | Vorlesung | |
| 10.1. | Übung | 14.1. | Vorlesung |
| 17.1. | Aktiv Session | 21.1. | Vorlesung |
| 24.1. | Übung | 28.1. | Vorlesung |
| 31.1. | Aktiv Session | 4.2. | Vorlesung |
| 7.2. | Übung | 11.2. | Vorlesung |
Vorlesung
- Konvexe Hülle: mit Klicks, ohne Klicks
- Linienschnitt: mit Klicks, ohne Klicks
- Triangulierung: mit Klicks, ohne Klicks
- LP und Schnitt von Halbebenen: mit Klicks, ohne Klicks
- Orthogonale Bereichsanfragen: mit Klicks, ohne Klicks
- Fractional Cascading: mit Klicks, ohne Klicks
- Point-Location und Persistenz: mit Klicks, ohne Klicks
- Voronoi-Diagramme: mit Klicks, ohne Klicks
- Origami: mit Klicks, ohne Klicks
- Schwere Probleme: mit Klicks, ohne Klicks
- Delaunay-Triangulierung: mit Klicks, ohne Klicks
- Real RAM, Word RAM: mit Klicks, ohne Klicks
- Geometrie: mit Klicks, ohne Klicks
- Geometrische Graphen: mit Klicks, ohne Klicks
- Zusammenfassung: mit Klicks, ohne Klicks
Zusatzinfos
Konvexe Hülle von Polygonen
- Liste mit den verschiedenen korrekten und inkorrekten Versuchen: A History of Linear-time Convex Hull Algorithms for Simple Polygons
- Algorithmus den wir uns angeschaut haben.
Speicherbedarf beim Linienschnitt & Clustering
Dualität
kd-Bäume
Fold and Cut
- Seite mit vielen weiteren Infos zum Thema: The Fold-and-Cut Problem
Algorithmische Geometrie bei der ESA 2021
Greedy Routing
Hyperbolisches Häkeln
Übungsblätter
- Blatt 1 (Abgabe bis 8.11.2021) blatt01.pdf
- Blatt 2 (Abgabe bis 22.11.2021) blatt02.pdf
- Blatt 3 (Abgabe bis 6.12.2021) blatt03.pdf und Nachtrag zum Bestimmen der Facettenlabel bei Map-Overlay
- Blatt 4 (Abgabe bis 20.12.2021) blatt04.pdf
- Blatt 5 (Abgabe bis 17.1.2022) blatt05.pdf
- Blatt 6 (Abgabe bis 31.1.2022 blatt06.pdf
- Blatt 7 (Abgabe bis 14.2.2022 blatt07.pdf