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

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

**Übungsleiter:** [[people:marcuswilhelm|]]
\\
\\

In der Vorlesung [[https://campus.studium.kit.edu/events/catalog.php#!campus/all/event.asp?gguid=0x55140A192EF44D95993A66BADFCE70C1|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 [[https://campus.studium.kit.edu/|Campus Management System]] anmelden.

/* Zur Terminfindung für die mündliche Prüfung bitte [[https://dudle.inf.tu-dresden.de/C1xvCzsPGQ/|hier]] eure Präferenz eintragen.
*/
===== Weihnachtsvorlesung (TGI) =====

Im Rahmen der Diesjährigen [[https://i11www.iti.kit.edu/teaching/winter2021/tgi/index|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 [[https://i11www.iti.kit.edu/teaching/winter2021/tgi/index|TGI Homepage]]. 

{{ :resources:mtg:tgi-weihnachts-vl.mp4?linkonly |Aufzeichnung der Weihnachtsvorlesung}}

/*

===== Ablauf =====

Wir treffen uns zum ersten Termin am **Freitag den 22.10.21 um 12 Uhr** in Raum 301. Danach treffen wir uns wöchentlich jeweils montags um 18 Uhr und Freitags um 12 Uhr in Raum 301. Im ersten Treffen wird der weitere Ablauf der Vorlesung besprochen.


Aufgrund von Corona sind folgende Einschränkungen zu beachten:
  * **3G:** Teilnahme und allgemein Aufenthalt im Gebäude ist nur mit 3G gestattet. Denkt also bitte an euren Impfnachweis; ohne 3G müssen wir euch leider wieder nach Hause schicken.
  * **Einchecken:** Vor dem Seminarraum gibt es einen QR-Code über den ihr euch selbstständig einchecken müsst.
  * **Masken:** Es besteht Maskenpflicht.

*/
===== Termine =====

^ Montag (18 Uhr)                                                    |^ Freitag (12 Uhr)              ||
|                         |                                           | 22.10.            | Vorlesung  |
| 25.10.            | Aktiv-Session                             | 29.10             | Vorlesung  |
| <del>1.11.</del> 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 =====
 
  - Konvexe Hülle: {{ :teaching:2021ws:comput_geom:01-konvexe-huelle.pdf |mit Klicks}}, {{ :teaching:2021ws:comput_geom:01-konvexe-huelle-print.pdf |ohne Klicks}}
  - Linienschnitt: {{ :teaching:2021ws:comput_geom:02-linien-schnitt.pdf |mit Klicks}}, {{ :teaching:2021ws:comput_geom:02-linien-schnitt-print.pdf |ohne Klicks}}
  - Triangulierung: {{ :teaching:2021ws:comput_geom:03-polygon-triangulierung.pdf |mit Klicks}}, {{ :teaching:2021ws:comput_geom:03-polygon-triangulierung-print.pdf |ohne Klicks}}
  - LP und Schnitt von Halbebenen: {{ :teaching:2021ws:comput_geom:04-lp-schnitt-halbebenen.pdf |mit Klicks}}, {{ :teaching:2021ws:comput_geom:04-lp-schnitt-halbebenen-print.pdf |ohne Klicks}}
  - Orthogonale Bereichsanfragen: {{ :teaching:2021ws:comput_geom:05-range-trees.pdf |mit Klicks}}, {{ :teaching:2021ws:comput_geom:05-range-trees-print.pdf |ohne Klicks}}
  - Fractional Cascading: {{ :teaching:2021ws:comput_geom:06-fractional-cascading.pdf |mit Klicks}}, {{ :teaching:2021ws:comput_geom:06-fractional-cascading-print.pdf |ohne Klicks}}
  - Point-Location und Persistenz: {{ :teaching:2021ws:comput_geom:07-point-location.pdf |mit Klicks}}, {{ :teaching:2021ws:comput_geom:07-point-location-print.pdf |ohne Klicks}}
  - Voronoi-Diagramme: {{ :teaching:2021ws:comput_geom:08-voronoi-diagramm.pdf |mit Klicks}}, {{ :teaching:2021ws:comput_geom:08-voronoi-diagramm-print.pdf |ohne Klicks}}
  - Origami: {{ :teaching:2021ws:comput_geom:09-origami.pdf |mit Klicks}}, {{ :teaching:2021ws:comput_geom:09-origami-print.pdf |ohne Klicks}}
  - Schwere Probleme: {{ :teaching:2021ws:comput_geom:10-hardness.pdf |mit Klicks}}, {{ :teaching:2021ws:comput_geom:10-hardness-print.pdf |ohne Klicks}}
  - Delaunay-Triangulierung: {{ :teaching:2021ws:comput_geom:11-delaunay-triangulierung.pdf |mit Klicks}}, {{ :teaching:2021ws:comput_geom:11-delaunay-triangulierung-print.pdf |ohne Klicks}}
  - Real RAM, Word RAM: {{ :teaching:2021ws:comput_geom:12-word-ram.pdf |mit Klicks}}, {{ :teaching:2021ws:comput_geom:12-word-ram-print.pdf |ohne Klicks}}
  - Geometrie: {{ :teaching:2021ws:comput_geom:13-geometrie.pdf |mit Klicks}}, {{ :teaching:2021ws:comput_geom:13-geometrie-print.pdf |ohne Klicks}}
  - Geometrische Graphen: {{ :teaching:2021ws:comput_geom:14-geometrische-graphen.pdf |mit Klicks}}, {{ :teaching:2021ws:comput_geom:14-geometrische-graphen-print.pdf |ohne Klicks}}
  - Zusammenfassung: {{ :teaching:2021ws:comput_geom:15-zusammenfassung.pdf |mit Klicks}}, {{ :teaching:2021ws:comput_geom:15-zusammenfassung-print.pdf |ohne Klicks}}

===== Zusatzinfos =====

== Konvexe Hülle von Polygonen ==

  * {{ :teaching:2021ws:comput_geom:aktiv-01.pdf |Folien aus der Aktivsession}}
  * 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:2021ws: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:2021ws:comput_geom:aktiv-03.pdf |Folien aus der Aktivsession}}

== kd-Bäume ==
  * {{ :teaching:2021ws:comput_geom:aktiv-04.pdf |Folien aus der Aktivsession}}

== Fold and Cut ==
  * {{ :teaching:2021ws: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]]

== Algorithmische Geometrie bei der ESA 2021 ==
  * {{ :teaching:2021ws:comput_geom:aktiv-06.pdf |Folien aus der Aktivsession}}
  * [[https://drops.dagstuhl.de/opus/volltexte/2021/14646/|The Visibility Center of a Simple Polygon]]
  * [[https://drops.dagstuhl.de/opus/volltexte/2021/14605/|An Instance-Optimal Algorithm for Bichromatic Rectangular Visibility]]
  * [[https://drops.dagstuhl.de/opus/volltexte/2021/14586/|The Voronoi Diagram of Rotating Rays with
Applications to Floodlight Illumination]]

== Greedy Routing ==
  * {{ :teaching:2021ws:comput_geom:aktiv-07.pdf |Folien aus der Aktivsession}}
  * [[https://dl.acm.org/doi/10.1109/INFCOM.2007.221|Geographic Routing Using Hyperbolic Space]]
  * [[https://dl.acm.org/doi/10.1145/3381751|Hyperbolic Embeddings for Near-Optimal Greedy Routing]]

== Hyperbolisches Häkeln ==
  * [[https://projecteuclid.org/ebooks/books-by-independent-authors/Experiencing%20Geometry/chapter/Appendix%20A.%20Making%20Models/10.3792/euclid/9781429799850-30|Link zu Anleitung für hyperbolische Kreisscheibe|]]
  * [[http://hyperbolic-crochet.blogspot.com/|Blog mit Inhalten zu hyperbolischer Geometrie und Häkeln]]
===== Übungsblätter =====

  * Blatt 1 (Abgabe bis 8.11.2021) {{ :teaching:2021ws:comput_geom:blatt01.pdf |}} 
  * Blatt 2 (Abgabe bis 22.11.2021) {{ :teaching:2021ws:comput_geom:blatt02.pdf |}}
  * Blatt 3 (Abgabe bis 6.12.2021) {{ :teaching:2021ws:comput_geom:blatt03.pdf |}} und [[teaching:2021ws:comput_geom:map-overlay-nachtrag|]]
  * Blatt 4 (Abgabe bis 20.12.2021) {{ :teaching:2021ws:blatt04.pdf |}}
  * Blatt 5 (Abgabe bis 17.1.2022) {{ :teaching:2021ws:comput_geom:blatt05.pdf |}}
  * Blatt 6 (Abgabe bis 31.1.2022 {{ :teaching:2021ws:comput_geom:blatt06.pdf |}}
  * Blatt 7 (Abgabe bis 14.2.2022 {{ :teaching:2021ws:comput_geom:blatt07.pdf |}}