Algorithmische Geometrie
Sommersemester 2014
Allgemeines
- Dozent: PD Dr. Martin Nöllenburg
- Übungsleiter Dr. Benjamin Niedermann
- 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 | VL11 | PR11 | [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] |
Zusatzmaterial
- Java Applet für Voronoi Diagramme der Uni Bonn
- Dualitäts-Applet von Universitat Politècnica de Catalunya, BarcelonaTech
- Beweis von Lemma 3 aus Vorlesung 12 (der Beweis ist in [M12] nicht ganz richtig)
- Applet zur inkrementellen Konstruktion von 3D konvexen Hüllen
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 |