Scalable Algorithms (ITI)

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.

Aufzeichnung der Weihnachtsvorlesung

Termine

Montag (18 Uhr) Freitag (12 Uhr)
22.10. Vorlesung
25.10. Aktiv-Session 29.10 Vorlesung
1.11. 2.11. Ü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

  1. Konvexe Hülle: mit Klicks, ohne Klicks
  2. Linienschnitt: mit Klicks, ohne Klicks
  3. Triangulierung: mit Klicks, ohne Klicks
  4. LP und Schnitt von Halbebenen: mit Klicks, ohne Klicks
  5. Orthogonale Bereichsanfragen: mit Klicks, ohne Klicks
  6. Fractional Cascading: mit Klicks, ohne Klicks
  7. Point-Location und Persistenz: mit Klicks, ohne Klicks
  8. Voronoi-Diagramme: mit Klicks, ohne Klicks
  9. Schwere Probleme: mit Klicks, ohne Klicks
  10. Delaunay-Triangulierung: mit Klicks, ohne Klicks
  11. Real RAM, Word RAM: mit Klicks, ohne Klicks
  12. Geometrie: mit Klicks, ohne Klicks
  13. Geometrische Graphen: mit Klicks, ohne Klicks
  14. Zusammenfassung: mit Klicks, ohne Klicks

Zusatzinfos

Konvexe Hülle von Polygonen
Speicherbedarf beim Linienschnitt & Clustering
Dualität
kd-Bäume
Fold and Cut
Algorithmische Geometrie bei der ESA 2021
Greedy Routing
Hyperbolisches Häkeln

Übungsblätter