====== Algorithmische Geometrie ======

**Dozent:** [[people:thomasblaesius|]]

**Übungsleiterin:** [[people:wendyyi|]]
\\
\\
In der Vorlesung [[https://campus.studium.kit.edu/search.php#!campus/all/abstractModuleView.asp?gguid=0x5209947B0865E0428A350951FD46F2EF|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 [[https://cloud.iti.kit.edu/index.php/apps/appointments/pub/ZTZppx4Iv4%2BSf0c01/form| 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.    | <del>Aktiv-Session</del>  |
| 11.12.    | Vorlesung      | 14.12.    | Übung                     |
| 18.12.    | Vorlesung      | 21.12.    | Aktiv-Session             |
|           |                |           |                           |
| 08.01.    | Vorlesung      | 11.01.    | Übung                     |
| 15.01.    | Vorlesung      | 18.01.    | <del>Aktiv-Session</del>  |
| 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 =====

  - Konvexe Hülle: {{ :teaching:2023ws:comput_geom:01-konvexe-huelle.pdf |mit Klicks}}, {{ :teaching:2023ws:comput_geom:01-konvexe-huelle-print.pdf |ohne Klicks}}
  - Linienschnitt: {{ :teaching:2023ws:comput_geom:02-linien-schnitt.pdf |mit Klicks}}, {{ :teaching:2023ws:comput_geom:02-linien-schnitt-print.pdf |ohne Klicks}}
  - Polygon-Triangulierung: {{ :teaching:2023ws:comput_geom:03-polygon-triangulierung.pdf |mit Klicks}}, {{ :teaching:2023ws:comput_geom:03-polygon-triangulierung-print.pdf |ohne Klicks}}
  - Lineare Programme & Schnitt von Halbebenen: {{ :teaching:2023ws:comput_geom:04-lp-schnitt-halbebenen.pdf |mit Klicks}}, {{ :teaching:2023ws:comput_geom:04-lp-schnitt-halbebenen-print.pdf |ohne Klicks}}
  - Orthogonale Bereichsanfragen - Range-Trees: {{ :teaching:2023ws:comput_geom:05-range-trees.pdf |mit Klicks}}, {{ :teaching:2023ws:comput_geom:05-range-trees-print.pdf |ohne Klicks}}
  - Orthogonale Bereichsanfragen - Fractional Cascading: {{ :teaching:2023ws:comput_geom:06-fractional-cascading.pdf |mit Klicks}}, {{ :teaching:2023ws:comput_geom:06-fractional-cascading-print.pdf |ohne Klicks}}
  - Point Location: {{ :teaching:2023ws:comput_geom:07-point-location.pdf |mit Klicks}}, {{ :teaching:2023ws:comput_geom:07-point-location-print.pdf |ohne Klicks}}
  - Voronoi Diagramme: {{ :teaching:2023ws:comput_geom:08-voronoi-diagramm.pdf |mit Klicks}}, {{ :teaching:2023ws:comput_geom:08-voronoi-diagramm-print.pdf |ohne Klicks}}
  - Origami: {{ :teaching:2023ws:comput_geom:09-origami.pdf |mit Klicks}}, {{ :teaching:2023ws:comput_geom:09-origami-print.pdf |ohne Klicks}}
  - Exkurs: Complexity of Voronoi Diagrams: {{ :teaching:2023ws:comput_geom:10-voronoi-higher-order.pdf |mit Klicks}}, {{ :teaching:2023ws:comput_geom:10-voronoi-higher-order-print.pdf |ohne Klicks}}
  - Delaunay Triangulierung: {{ :teaching:2023ws:comput_geom:11-delaunay-triangulierung.pdf |mit Klicks}}, {{ :teaching:2023ws:comput_geom:11-delaunay-triangulierung-print.pdf |ohne Klicks}}
  - Schwere Probleme: {{ :teaching:2023ws:comput_geom:12-hardness.pdf |mit Klicks}}, {{ :teaching:2023ws:comput_geom:12-hardness-print.pdf |ohne Klicks}}
  - Real RAM, Word RAM, Point Location: {{ :teaching:2023ws:comput_geom:13-word-ram.pdf |mit Klicks}}, {{ :teaching:2023ws:comput_geom:13-word-ram-print.pdf |ohne Klicks}}
  - Geometrie: {{ :teaching:2023ws:comput_geom:14-geometrie.pdf |mit Klicks}}, {{ :teaching:2023ws:comput_geom:14-geometrie-print.pdf |ohne Klicks}}
  - Geometrische Graphen: {{ :teaching:2023ws:comput_geom:15-geometrische-graphen.pdf |mit Klicks}}, {{ :teaching:2023ws:comput_geom:15-geometrische-graphen-print.pdf |ohne Klicks}}
  - Zusammenfassung: {{ :teaching:2023ws:comput_geom:16-zusammenfassung.pdf |mit Klicks}}, {{ :teaching:2023ws:comput_geom:16-zusammenfassung-print.pdf |ohne Klicks}}
===== Übungen =====
  - Doppelt verkettete Kantenliste,  konvexe Hülle: {{ :teaching:2023ws:comput_geom:01-uebung.pdf |Übung 1}}
  - Blatt 1, Art Gallery Problem: {{ :teaching:2023ws:comput_geom:02-uebung.pdf |Übung 2}}
  - Blatt 2, Range Trees: {{ :teaching:2023ws:comput_geom:03-uebung.pdf |Übung 3}}
  - Blatt 3, Range Trees/Persistenz: {{ :teaching:2023ws:comput_geom:04-uebung.pdf |Übung 4}}
  - Blatt 4, Voronoi-Diagramm von Strecken: {{ :teaching:2023ws:comput_geom:05-uebung.pdf |Übung 5}}
  - Blatt 5, Türen-Problem: {{ :teaching:2023ws:comput_geom:06-uebung.pdf |Übung 6}}
  - Blatt 6, Tilings: {{ :teaching:2023ws:comput_geom:07-uebung.pdf |Übung 7}}
===== Übungsblätter =====
{{ :teaching:2023ws:comput_geom:blatt01.pdf | Übungsblatt 01}}

{{ :teaching:2023ws:comput_geom:blatt02.pdf | Übungsblatt 02}}

{{ :teaching:2023ws:comput_geom:blatt03.pdf | Übungsblatt 03}}

{{ :teaching:2023ws:comput_geom:blatt04.pdf | Übungsblatt 04}}

{{ :teaching:2023ws:comput_geom:blatt05.pdf | Übungsblatt 05}}

{{ :teaching:2023ws:comput_geom:blatt06.pdf | Übungsblatt 06}}

{{ :teaching:2023ws:comput_geom:blatt07.pdf | Übungsblatt 07}}
===== Aktivsessions =====

== Konvexe Hülle von Polygonen ==

  * {{ :teaching:2023ws:comput_geom:aktiv-01.pdf |Folien aus der Aktivsession}}
  * {{ :teaching:2023ws:comput_geom:aktiv-01-fehler.pdf |Gegenbeispiel für den falschen Algorithmus}}
  * Liste mit den verschiedenen korrekten und inkorrekten Versuchen: [[http://cgm.cs.mcgill.ca/~athens/cs601/|A History of Linear-time Convex Hull Algorithms for Simple Polygons]]
  * [[http://cgm.cs.mcgill.ca/~athens/cs601/Melkman.html|Algorithmus]] den wir uns angeschaut haben.

== Speicherbedarf beim Linienschnitt & Clustering ==
  * {{ :teaching:2023ws:comput_geom:aktiv-02.pdf |Folien aus der Aktivsession}}
  * Link zum Paper: [[https://epubs.siam.org/doi/10.1137/0220029|On Vertical Visibility in Arrangements of Segments and
the Queue Size in the Bentley-Ottmann Line Sweeping
Algorithm]]


== Dualität ==

  * {{ :teaching:2023ws:comput_geom:aktiv-03.pdf |Folien aus der Aktivsession}}


== Fold and Cut ==
  * {{ :teaching:2023ws:comput_geom:fold-and-cut.pdf |Folien aus der Aktivsession}}
  * Seite mit vielen weiteren Infos zum Thema: [[http://erikdemaine.org/foldcut/|The Fold-and-Cut Problem]]

== Greedy Routing ==
  * {{ :teaching:2023ws:comput_geom:aktiv-07.pdf |Folien aus der Aktivsession}}