Institut für Theoretische Informatik, Algorithmik
Suche
Institut für Theoretische Informatik, Algorithmik
Institut für Theoretische Informatik, Algorithmik
Institut für Theoretische Informatik, Algorithmik
Lehre
Sommersemester 2014
Algorithmische Geometrie

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 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]

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