Algorithmische Geometrie

Dozent: Thomas Bläsius

Übungsleiterin: Wendy Yi

In der Vorlesung Algorithmische Geometrie beschäftigen wir uns mit dem Entwurf und der Analyse geometrischer Algorithmen und Datenstrukturen.

Ablauf

Wir treffen uns jede Woche montags um 15:45 und donnerstags um 14:00 Uhr in Raum 301. Die erste Vorlesung wird am Montag den 23.10. um 15:45 stattfinden.

Prüfung

Ihr könnt einen Termin für die mündliche Prüfung hier buchen. Fragen diesbezüglich gerne an Isabelle Junge (scale.info@iti.kit.edu, Sekretariat)

Termine

Mo 15:45 Do 14:00
23.10. Vorlesung 26.10. Aktiv-Session
30.10. Vorlesung 02.11. Übung
06.11. Vorlesung 09.11. Aktiv-Session
13.11. Vorlesung 16.11. Übung
20.11. Vorlesung 23.11. Aktiv-Session
27.11. Vorlesung 30.12. Übung
04.12. Vorlesung 07.12. Aktiv-Session
11.12. Vorlesung 14.12. Übung
18.12. Vorlesung 21.12. Aktiv-Session
08.01. Vorlesung 11.01. Übung
15.01. Vorlesung 18.01. Aktiv-Session
22.01. Vorlesung 25.01. Übung
29.01. Vorlesung 01.02. Vorlesung
05.02. Aktiv-Session 08.02. Übung
12.02. Vorlesung 15.02. Zusammenfassung

Vorlesung

  1. Konvexe Hülle: mit Klicks, ohne Klicks
  2. Linienschnitt: mit Klicks, ohne Klicks
  3. Polygon-Triangulierung: mit Klicks, ohne Klicks
  4. Lineare Programme & Schnitt von Halbebenen: mit Klicks, ohne Klicks
  5. Orthogonale Bereichsanfragen - Range-Trees: mit Klicks, ohne Klicks
  6. Orthogonale Bereichsanfragen - Fractional Cascading: mit Klicks, ohne Klicks
  7. Point Location: mit Klicks, ohne Klicks
  8. Voronoi Diagramme: mit Klicks, ohne Klicks
  9. Origami: mit Klicks, ohne Klicks
  10. Exkurs: Complexity of Voronoi Diagrams: mit Klicks, ohne Klicks
  11. Delaunay Triangulierung: mit Klicks, ohne Klicks
  12. Schwere Probleme: mit Klicks, ohne Klicks
  13. Real RAM, Word RAM, Point Location: mit Klicks, ohne Klicks
  14. Geometrie: mit Klicks, ohne Klicks
  15. Geometrische Graphen: mit Klicks, ohne Klicks
  16. Zusammenfassung: mit Klicks, ohne Klicks

Übungen

  1. Doppelt verkettete Kantenliste, konvexe Hülle: Übung 1
  2. Blatt 1, Art Gallery Problem: Übung 2
  3. Blatt 2, Range Trees: Übung 3
  4. Blatt 3, Range Trees/Persistenz: Übung 4
  5. Blatt 4, Voronoi-Diagramm von Strecken: Übung 5
  6. Blatt 5, Türen-Problem: Übung 6
  7. Blatt 6, Tilings: Übung 7

Übungsblätter

Übungsblatt 01

Übungsblatt 02

Übungsblatt 03

Übungsblatt 04

Übungsblatt 05

Übungsblatt 06

Übungsblatt 07

Aktivsessions

Konvexe Hülle von Polygonen
Speicherbedarf beim Linienschnitt & Clustering
Dualität
Fold and Cut
Greedy Routing