Algorithmische Geometrie

Sommersemester 2012

Allgemeines

  • Dozent: Dr. Martin Nöllenburg
  • Übungsleiter Dipl.-Inform. Andreas Gemsa
  • Vorlesung: dienstags 9:45 - 11:15, erstmalig am 17. April, Raum 301 (Infobau Geb. 50.34)
  • Übung: donnerstags 10:15 - 11:00, erstmalig am 26. April, Raum 131 (Infobau Geb. 50.34)
  • Credits: Im Masterstudiengang werden für diese Veranstaltung 5 Credits vergeben
  • Prüfung: Im Diplomstudiengang mit 2 SWS in den Vertiefungsfächern Algorithmentechnik, Theoretische Grundlagen, Computergrafik prüfbar.

Aktuelles

  • Die nächste Übung (am 24. Mai) beginnt bereits um 9:45 Uhr in Raum 131.
  • Die nächste Übung (am 10. Mai) beginnt bereits um 9:45 Uhr in Raum 131.

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.

Termine

Datum Thema Folien Druckversion Literatur
17.04. Vorlesung Einführung, konvexe Hülle VL01 PR01 [BCKO08] Kap. 1
24.04. Vorlesung Streckenschnitte VL02PR02 [BCKO08] Kap. 2, [K05] Kap. 2.3.2
26.04. Übung (Raum 131) konvexe Hülle UB01
01.05. Feiertag
03.05. Vorlesung (Raum 131) Polygontriangulierung VL03 PR03 [BCKO08] Kap. 3, [K05] Kap. 4.3.3, [OR87]
08.05. Vorlesung Lineares Programmieren VL04 PR04 [BCKO08] Kap. 4
10.05. 9:45–11:15 Uhr Übung (Raum 131) Streckenschnitte/Polygontriangulierung UB02
15.05. Vorlesung Bereichsabfragen VL05 PR05 [BCKO08] Kap. 5, [K05] Kap. 3.3
22.05. Vorlesung Punktlokalisierung [BCKO08] Kap. 6
24.05. 9:45–11:15 Uhr Übung (Raum 131) Bereichsabfragen/Lineares Programmieren

Änderungen vorbehalten. Vorlesungsfolien nutzen z.T. die Folien von Prof. Alexander Wolff, Uni Würzburg als Vorlage.

Übungsblätter

Ausgabe Abgabe Thema PDF ML
17.04. 24.04. Konvexe Hülle ueb01
24.04. 03.05. Streckenschnitte ueb02
01.05. 08.05. Polygontriangulierung ueb03
08.05. 15.05. Lineare Programmierung ueb04
15.05. 22.05. Bereichsanfragen ueb05

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.
[M10] D. Mount: Lecture Notes CMSC 754 Computational Geometry, taught at U Maryland, 2010.
[OR87] J. O'Rourke: Art Gallery Theorems and Algorithms, Oxford University Press, 1987.