====== Algorithmische Geometrie ====== **Dozent:** [[people:thomasblaesius|]] **Übungsleiter:** [[people:marcuswilhelm|]] \\ \\ In der Vorlesung [[https://campus.studium.kit.edu/events/catalog.php#!campus/all/event.asp?gguid=0xF206F55F1F174712BEE4254CBB54984D&rwfiguid=0xBA017CDBC86740258C73857EAF8A993A|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 [[https://campus.studium.kit.edu/|Campus Management System]] nötig. Anschließend muss per Email an [[https://i11www.iti.kit.edu/members/laurette_lauffer/index|Tanja Wehrmann]] () 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 [[https://ilias.studium.kit.edu/goto.php?target=crs_1297029_rcodec7Cf9MfktA&client_id=produktiv |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 ===== - Konvexe Hülle: {{ :teaching:2020ws:01-konvexe-huelle.pdf |mit Klicks}}, {{ :teaching:2020ws:01-konvexe-huelle-print.pdf |ohne Klicks}} - Linienschnitt: {{ :teaching:2020ws:comput_geom:02-linien-schnitt.pdf |mit Klicks}}, {{ :teaching:2020ws:comput_geom:02-linien-schnitt-print.pdf |ohne Klicks}}, {{ :teaching:2020ws:comput_geom:video:02-linienschnitt-1080p.mp4?linkonly|Aufnahme (1080p, 337 MB)}}, {{ :teaching:2020ws:comput_geom:video:02-linienschnitt-720p.mp4?linkonly|Aufnahme (720p, 175 MB)}} - Polygontriangulierung: {{ :teaching:2020ws:comput_geom:03-polygon-triangulierung.pdf |mit Klicks}}, {{ :teaching:2020ws:comput_geom:03-polygon-triangulierung-print.pdf |ohne Klicks}}, {{ :teaching:2020ws:comput_geom:video:03-polygon-triangulierung-1080p.mp4?linkonly|Aufnahme (1080p, 330 MB)}}, {{ :teaching:2020ws:comput_geom:video:03-polygon-triangulierung-720p.mp4?linkonly| Aufnahme (720p, 173 MB)}} - Lineare Programme & Schnitt von Halbebenen: {{ :teaching:2020ws:comput_geom:04-lp-schnitt-halbebenen.pdf |mit Klicks}}, {{ :teaching:2020ws:comput_geom:04-lp-schnitt-halbebenen-print.pdf |ohne Klicks}}, {{ :teaching:2020ws:comput_geom:video:04-lp-schnitt-halbebenen-1080p.mp4?linkonly|Aufnahme (1080p, 372 MB)}}, {{ :teaching:2020ws:comput_geom:video:04-lp-schnitt-halbebenen-720p.mp4?linkonly|Aufname (720p, 175 MB)}} - Range Trees: {{ :teaching:2020ws:comput_geom:05-range-trees.pdf |mit Klicks}}, {{ :teaching:2020ws:comput_geom:05-range-trees-print.pdf |ohne Klicks}}, {{ :teaching:2020ws:comput_geom:video:05-range-trees-1080p.mp4?linkonly|Aufnahme (1080p, 309 MB)}}, {{ :teaching:2020ws:comput_geom:video:05-range-trees-720p.mp4?linkonly|Aufnahme (720p, 153 MB)}} - Fractional Cascading: {{ :teaching:2020ws:comput_geom:06-fractional-cascading.pdf |mit Klicks}}, {{ :teaching:2020ws:comput_geom:06-fractional-cascading-print.pdf |ohne Klicks}}, {{ :teaching:2020ws:comput_geom:video:06-fractional-cascading-1080p.mp4?linkonly|Aufnahme (1080p, 351 MB)}}, {{ :teaching:2020ws:comput_geom:video:06-fractional-cascading-720p.mp4?linkonly|Aufnahme (720p, 183 MB)}} - Point Location: {{ :teaching:2020ws:comput_geom:07-point-location.pdf |mit Klicks}}, {{ :teaching:2020ws:comput_geom:07-point-location-print.pdf |ohne Klicks}}, {{ :teaching:2020ws:comput_geom:video:07-point-location-1080p.mp4?linkonly|Aufnahme (1080p, 354 MB)}}, {{ :teaching:2020ws:comput_geom:video:07-point-location-720p.mp4?linkonly|Aufnahme (720p, 184 MB)}} - Voronoi-Diagramme: {{ :teaching:2020ws:comput_geom:08-voronoi-diagramm.pdf |mit Klicks}}, {{ :teaching:2020ws:comput_geom:08-voronoi-diagramm-print.pdf |ohne Klicks}}, {{ :teaching:2020ws:comput_geom:video:08-voronoi-diagramme-1080p.mp4?linkonly|Aufnahme (1080p, 355 MB)}}, {{ :teaching:2020ws:comput_geom:video:08-voronoi-diagramme-720p.mp4?linkonly|Aufnahme (720p, 180 MB)}} - Delaunay-Triangulierung: {{ :teaching:2020ws:comput_geom:09-delaunay-triangulierung.pdf |mit Klicks}}, {{ :teaching:2020ws:comput_geom:09-delaunay-triangulierung-print.pdf |ohne Klicks}}, {{ :teaching:2020ws:comput_geom:video:09-delaunay-triangulierung-1080p.mp4?linkonly|Aufnahme (1080p, 238 MB)}}, {{ :teaching:2020ws:comput_geom:video:09-delaunay-triangulierung-720p.mp4?linkonly|Aufnahme (720p, 126 MB)}} - Schwere Probleme: {{ :teaching:2020ws:comput_geom:10-hardness.pdf |mit Klicks}}, {{ :teaching:2020ws:comput_geom:10-hardness-print.pdf |ohne Klicks}}, {{ :teaching:2020ws:comput_geom:video:10-schwere-probleme-1080p.mp4?linkonly|Aufnahme (1080p, 355 MB)}}, {{ :teaching:2020ws:comput_geom:video:10-schwere-probleme-720p.mp4?linkonly|Aufnahme (720p, 186 MB)}} - Real RAM, Word RAM: {{ :teaching:2020ws:comput_geom:11-word-ram.pdf |mit Klicks}}, {{ :teaching:2020ws:comput_geom:11-word-ram-print.pdf |ohne Klicks}} {{ :teaching:2020ws:comput_geom:video:11-word-ram-1080p.mp4?linkonly|Aufnahme (1080p, 426 MB)}}, {{ :teaching:2020ws:comput_geom:video:11-word-ram-720p.mp4?linkonly|Aufnahme (720p, 204 MB)}} - Geometrie: {{ :teaching:2020ws:comput_geom:12-geometrie.pdf |mit Klicks}}, {{ :teaching:2020ws:comput_geom:12-geometrie-print.pdf |ohne Klicks}}, {{ :teaching:2020ws:comput_geom:video:12-geometrie-1080p.mp4?linkonly|Aufnahme (1080p, 384 MB)}}, {{ :teaching:2020ws:comput_geom:video:12-geometrie-720p.mp4?linkonly|Aufnahme (720p, 201 MB)}} - Geometrische Zufallsgraphen: {{ :teaching:2020ws:comput_geom:13-geometrische-zufallsgraphen.pdf |mit Klicks}}, {{ :teaching:2020ws:comput_geom:13-geometrische-zufallsgraphen-print.pdf |ohne Klicks}}, {{ :teaching:2020ws:comput_geom:video:13-geometrische-zufallsgraphen-1080p.mp4?linkonly|Aufnahme (1080p, 380 MB)}}, {{ :teaching:2020ws:comput_geom:video:13-geometrische-zufallsgraphen-720p.mp4?linkonly|Aufnahme (720p, 188 MB)}} - Zusammenfassung: {{ :teaching:2020ws:comput_geom:14-zusammenfassung.pdf |mit Klicks}}, {{ :teaching:2020ws:comput_geom:14-zusammenfassung-print.pdf |ohne Klicks}}, {{ :teaching:2020ws:comput_geom:video:14-zusammenfassung-1080p.mp4?linkonly |Aufnahme (1080p, 307 MB)}}, {{ :teaching:2020ws:comput_geom:video:14-zusammenfassung-720p.mp4?linkonly | Aufnahme (720p, 160 MB)}} ===== Zusatzinfos ===== * [[http://cgm.cs.mcgill.ca/~athens/cs601/|Richtige und falsche Algorithmen für konvexe Hülle von einfachen Polygonen]] (der korrekte Algorithmus, den wir noch kurz angerissen haben, ist der von 1987 Melkman). * {{ :teaching:2020ws:comput_geom:fold-and-cut.pdf |Fold-and-Cut "Folien"}} * {{ :teaching:2020ws:comput_geom:aktiv-06.pdf |Clustering & EMST}} * {{ :teaching:2020ws:comput_geom:aktiv-07.pdf |Greedy Routing}} ===== Übungsblätter ===== * Blatt 0 (Abgabe bis 11.11.2020) {{:teaching:2020ws:comput_geom:blatt00.pdf |blatt00.pdf}} * Blatt 1 (Abgabe bis 25.11.2020) {{:teaching:2020ws:comput_geom:blatt01.pdf |blatt01.pdf}} * Blatt 2 (Abgabe bis 9.12.2020) {{:teaching:2020ws:comput_geom:blatt02.pdf |blatt02.pdf}} * Blatt 3 (Abgabe bis 23.12.2020) {{:teaching:2020ws:comput_geom:blatt03.pdf |blatt03.pdf}} * Blatt 4 (Abgabe bis 20.1.2021) {{:teaching:2020ws:comput_geom:blatt04.pdf |blatt04.pdf}} * Blatt 5 (Abgabe bis 3.2.2021) {{:teaching:2020ws:comput_geom:blatt05.pdf |blatt05.pdf}} * Blatt 6 (Abgabe bis 17.2.2021) {{:teaching:2020ws:comput_geom:blatt06.pdf |blatt06.pdf}} Template für Musterlösung: {{:teaching:2020ws:comput_geom:template.zip|template.zip}}