Algorithmische Geometrie

Sommersemester 2014

Allgemeines

  • Vorlesung: dienstags 9:45 - 11:15, erstmalig am 15. April, Raum 301 (Infobau Geb. 50.34)
  • Übung: mittwochs 15:45 - 16:30/17:15, erstmalig am 16. April, Raum 301 (Infobau Geb. 50.34)
  • Module: im Master Informatik prüfbar in den Modulen Algorithmische Geometrie, Algorithm Engineering und Anwendungen, Design und Analyse von Algorithmen, Algorithmen der Computergrafik
  • Credits: Master: 5 LP (Ausnahme: 3 LP im Modul Algorithmen der Computergrafik), Diplom: 2 SWS
  • Prüfung: Die mündliche Prüfung besteht aus einer semesterbegleitenden Projektarbeit (20%) und einer 20-minütigen Abschlussprüfung (80%). Die Prüfungstermine sind zunächst 6. August und 8. Oktober. Anmeldung per Mail an Lilian Beckert.

Aktuelles

  • Projekte sind online
  • nächste Prüfungstermine am 6.8. und 8.10. (Anmeldung per Mail an Lilian Beckert)
  • Projektpräsentationen in der Übung am 2.7. und 9.7.
  • Vorlesung im Diplomstudiengang mit 2 SWS prüfbar
  • Mittwoch, 7.5. Vergabe der Projektthemen in der Übung
  • Link zu Beweisen der Eulerformel unter Zusatzmaterial

Thema

Räumliche Daten werden in den unterschiedlichsten Bereichen der Informatik verarbeitet, z.B. in Computergrafik und Visualisierung, in geographischen Informationssystemen, in der Robotik usw. Die algorithmische Geometrie beschäftigt sich mit dem Entwurf und der Analyse geometrischer Algorithmen und Datenstrukturen. In dieser Veranstaltung werden häufig verwendete Techniken und Konzepte der algorithmischen Geometrie vorgestellt und anhand ausgewählter und anwendungsbezogener Fragestellungen vertieft.

Projekte

Im Rahmen der Vorlesung implementierten die teilnehmenden Studenten einige geometrische Algorithmen und Datenstrukturen, die in der Vorlesung diskutiert wurden. Die Projekte werden auf der folgenden Seite vorgestellt: Visualizations of Algorithms in Computational Geometry.

Termine

Vorlesung

Datum Thema Folien Druckversion Literatur
15.04. Einführung, konvexe Hülle VL01 PR01 [BCKO08, Kap.1], [CH96]
22.04. Linienschnitte VL02 PR02 [BCKO08, Kap.2]
29.04. Polygontriangulierung VL03 PR03 [BCKO08, Kap.3]
06.05. Lineares Programmieren in 2D VL04 PR04 [BCKO08, Kap.4]
13.05. Bereichsabfragen VL05 PR05 [BCKO08, Kap.5]
20.05. Bereichsabfragen II VL06 PR06 [BCKO08, Kap.10]
27.05. Punktlokalisierung VL07 PR07 [BCKO08, Kap.6]
03.06. Voronoi-Diagramme VL08 PR08 [BCKO08, Kap.7]
10.06. Delaunay-Triangulierungen VL09 PR09 [BCKO08, Kap.9]
17.06. Dualität VL10 PR10 [BCKO09, Kap.8.(2-3)], [M12, Lec.8,14,15]
24.06. Quadtrees VL11PR11 [BCKO09, Kap.14]
01.07. Well-Separated Pair Decomposition VL12 PR12 [M12, Lec. 18+19]; Beweis von Lem3; noch mehr Details zu QTs und WSPD: [HP08]
08.07. WSPD: Anwendungen; Sichtbarkeitsgraphen VL13 PR13 [M12, Lec.19], [BCKO09, Kap.15]
15.07. Konvexe Hüllen in 3D VL14 PR14 [BCKO09, Kap.11], [M12, Lec.28]

Übung

Datum Thema Folien
16.04. Einführung, Grundlegende Datenstrukturen Übung 1
23.04. entfällt
30.04. Konvexe Hülle, Streckenschnitte Übung 2
07.05. Polygontriangulierung Übung 3
14.05. Lineare Programmierung Übung 4
21.05. Bereichsabfrage Übung 5
28.05. Bereichsabfrage II Übung 6
04.06. Punktlokalisierung Übung 7
11.06. Voronoi-Diagramme Übung 8
18.06. Delaunay-Triangulierungen Übung 9
25.06. Dualität Übung 10
02.07. Quad-Tree Übung 11
09.07. WSPD Übung 12
16.07. Sichtbarkeitsgraph Übung 13

Änderungen vorbehalten.

Übungsblätter

Ausgabe Abgabe Thema PDF ML
16.04.1422.04.14Konvexe Hüllen ÜB1 ML1
22.04.1429.04.14Streckenschnitte ÜB2 ML2
29.04.1406.05.14Polygontriangulierung ÜB3 ML3
06.05.1413.05.14Lineare Programmierung ÜB4 ML4
13.05.1420.05.14Bereichsabfrage ÜB5 ML5
20.05.1427.05.14Bereichsabfrage II ÜB6 ML6
27.05.1403.06.14Punktanfrage ÜB7 ML7
03.06.1410.06.14Voronoi-Diagramme ÜB8 ML8
10.06.1417.06.14Delauney Triangulierung ÜB9 ML9
17.06.1424.06.14Dualität ÜB10 ML10
24.06.1401.07.14Quadtrees ÜB11 ML11
01.07.1408.07.14WSPD ÜB12 ML12
08.07.1415.07.14Sichtbarkeitsgraph ÜB13 ML13

Zusatzmaterial

Literatur und Skripte

[BCKO08] M. de Berg, O. Cheong, M. van Kreveld, M. Overmars: Computational Geometry, 3rd ed., Springer-Verlag, 2008.
[HP08] S. Har-Peled: Geometric Approximation Algorithms, Preprint, 2008.
[K05] R. Klein: Algorithmische Geometrie, 2nd ed., Springer-Verlag, 2005.
[M02] D. Mount: Lecture Notes CMSC 754 Computational Geometry, taught at U Maryland, 2002.
[M12] D. Mount: Lecture Notes CMSC 754 Computational Geometry, taught at U Maryland, 2012.
[OR87] J. O'Rourke: Art Gallery Theorems and Algorithms, Oxford University Press, 1987.
[CH96] T. Chan: Optimal output-sensitive convex hull algorithms in two and three dimensions, Discrete & Computational Geometry, vol. 16, pp. 361-368, 1996