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.

Mündliche Prüfung

Zeitpunkt: Die Prüfung findet an den Tagen 24. Februar und 25. März statt. Mögliche Uhrzeiten sind zwischen 9:00 und 15:00 Uhr.

Anmeldung: Um an der Prüfung Teilzunehmen ist eine Anmeldung über das Campus Management System nötig. Anschließend muss per Email an Tanja Wehrmann (tanja.wehrmann@kit.edu) ein Zeitpunkt ausgemacht werden.

Ablauf

Wir treffen uns zum ersten Termin am Mittwoch den 4.11.20 um 8 Uhr in digitaler Form. Der Link zum Zoom Meeting ist im Ankündigungsforum des ILIAS-Kurses zu finden. Im ersten Treffen wird der weitere Ablauf der Vorlesung besprochen. Danach treffen wir uns wöchentlich, jeweils mittwochs um 8 und freitags um 12 Uhr.

Termine

Mittwoch (8 Uhr) Freitag (12 Uhr)
4.11. Vorlesung 6.11. Übung
11.11. Aktiv-Session 13.11. Vorlesung
18.11. Übung 20.11. Vorlesung
25.11. Aktiv-Session 27.11. Vorlesung
2.12. Übung 4.12. Vorlesung
9.12. Aktiv-Session 11.12. Vorlesung
16.12. Übung 18.12. Vorlesung
23.12. Aktiv-Session
8.1. Vorlesung
13.1. Übung 15.1. Vorlesung
20.1. Aktiv-Session 22.1. Vorlesung
27.1. Übung 29.1. Vorlesung
3.2. Aktiv-Session 5.2. Vorlesung
10.2. Übung 12.2. Vorlesung
17.2. Aktiv-Session 19.2. Vorlesung

Vorlesung

  1. Konvexe Hülle: mit Klicks, ohne Klicks
  2. Linienschnitt: mit Klicks, ohne Klicks, Aufnahme (1080p, 337 MB), Aufnahme (720p, 175 MB)
  3. Polygontriangulierung: mit Klicks, ohne Klicks, Aufnahme (1080p, 330 MB), Aufnahme (720p, 173 MB)
  4. Lineare Programme & Schnitt von Halbebenen: mit Klicks, ohne Klicks, Aufnahme (1080p, 372 MB), Aufname (720p, 175 MB)
  5. Range Trees: mit Klicks, ohne Klicks, Aufnahme (1080p, 309 MB), Aufnahme (720p, 153 MB)
  6. Fractional Cascading: mit Klicks, ohne Klicks, Aufnahme (1080p, 351 MB), Aufnahme (720p, 183 MB)
  7. Point Location: mit Klicks, ohne Klicks, Aufnahme (1080p, 354 MB), Aufnahme (720p, 184 MB)
  8. Voronoi-Diagramme: mit Klicks, ohne Klicks, Aufnahme (1080p, 355 MB), Aufnahme (720p, 180 MB)
  9. Delaunay-Triangulierung: mit Klicks, ohne Klicks, Aufnahme (1080p, 238 MB), Aufnahme (720p, 126 MB)
  10. Schwere Probleme: mit Klicks, ohne Klicks, Aufnahme (1080p, 355 MB), Aufnahme (720p, 186 MB)
  11. Real RAM, Word RAM: mit Klicks, ohne Klicks Aufnahme (1080p, 426 MB), Aufnahme (720p, 204 MB)
  12. Geometrie: mit Klicks, ohne Klicks, Aufnahme (1080p, 384 MB), Aufnahme (720p, 201 MB)
  13. Geometrische Zufallsgraphen: mit Klicks, ohne Klicks, Aufnahme (1080p, 380 MB), Aufnahme (720p, 188 MB)
  14. Zusammenfassung: mit Klicks, ohne Klicks, Aufnahme (1080p, 307 MB), Aufnahme (720p, 160 MB)

Zusatzinfos

Übungsblätter

Template für Musterlösung: template.zip