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 2012
Algorithmische Geometrie

Algorithmische Geometrie

Sommersemester 2012

Allgemeines

  • Dozent: PD Dr. Martin Nöllenburg
  • Übungsleiter Dr. 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ächsten Prüfungstermine sind am 27. September und am 18. Oktober. Zur Anmeldung wenden Sie sich bitte an das Sekretariat. Weitere Termine nach Vereinbarung.
  • Die Musterlösungen der bisher in den Übungen besprochenen Übungsblätter sind online. Bei Fragen zu den MLs oder zu Inhalten der Übung per Mail an Andreas Gemsa.
  • Die nächste Übung (am 12. Juli) beginnt bereits um 9:45 Uhr in Raum 131.
  • neue Applets unter Zusatzmaterial
  • Am 05.07. findet keine Übung statt.
  • Ein möglicher Prüfungstermin vor der Sommerpause ist am Freitag, 20. Juli. Sollten Sie sich an diesem Tag prüfen lassen wollen, setzen Sie sich bitte mit dem Sekretariat in Verbindung. Der nächste mögliche Termin ist dann wieder der 27. September. Danach wird es weitere Termine im September/Oktober geben.
  • 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 konvexe Hülle UB01 [CH96]
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. Übung Streckenschnitte/Polygontriangulierung UB02
15.05. Vorlesung Bereichsabfragen VL05 PR05 [BCKO08] Kap. 5, [K05] Kap. 3.3
22.05. Vorlesung Punktlokalisierung VL06PR06 [BCKO08] Kap. 6
24.05. Übung Bereichsabfragen/Lineares Programmieren UB03
29.05. Vorlesung Voronoi-Diagramme VL07PR07 [BCKO08] Kap. 7, [K05] Kap. 5.2, 6.3
31.05. Übung Punktlokalisierung UB04
05.06. Vorlesung Delaunay-Triangulierung VL08 PR08[BCKO08] Kap. 9, [K05] Kap. 5.4
12.06. Vorlesung Arrangements und Dualität VL09PR09 [BCKO08] Kap. 8.2, 8.3, 11.4, [M10] Lect. 7, 14, 15
14.06. Übung Voronoi-Diagramme/Delaunay-Triangulierung UB05
19.06. Vorlesung Quadtrees VL10 PR10 [BCKO08] Kap. 14
21.06. Übung Dualität UB06 Applet
26.06. Vorlesung Konvexe Hülle im 3-dimensionalen VL11 PR11 [BCKO08] Kap. 4, Kap. 11
28.06. Übung (Raum 131) Quadtrees UB07
03.07. Vorlesung Well-Separated Pair Decomposition VL12 PR12 [M10] Lect. 18+19; noch mehr Details zu QTs und WSPD: [HP08]
10.07. Vorlesung Anwendungen WSPD, Sichtbarkeitsgraphen VL13 PR13 [M10] Lect. 18+19, [BCKO08] Kap. 13.2 + 15
12.07. Übung Konvexe Hülle in 3D + WSPD UB08
17.07. Vorlesung Bereichsabfragen II VL14 PR14 [BCKO08] Kap. 10
19.07. Übung Sichtbarkeitsgraphen UB09

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

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.
[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.
[CH96] T. Chan: Optimal output-sensitive convex hull algorithms in two and three dimensions, Discrete & Computational Geometry, vol. 16, pp. 361-368, 1996