Algorithmische Geometrie

Dr. Sonja Maier
Wintertrimester 2014

[Überblick] [Termine] [Dateien] [Literatur]

Überblick

Die Algorithmische Geometrie beschäftigt sich mit der effizienten Speicherung und Verarbeitung geometrischer Daten, v.a. in Form von Punkten, Linien, Kreisen, Polygonen und Körpern. Sie widmet sich dabei der Entwicklung von effizienten und praktikablen Algorithmen zur Lösung geometrischer Probleme und der Bestimmung ihrer algorithmischen Komplexität. Anwendungen erfährt die Algorithmische Geometrie beispielsweise in der Computergrafik, im Computer Aided Design, für Geoinformationssysteme und in der Robotik, insbesondere bei der Planung von Bewegungsabläufen. In der Veranstaltung werden Fragestellungen untersucht wie z.B. die Nächstnachbarsuche, die effiziente Bestimmung von Schnittmengen in Mengen von Liniensegmenten oder Rechtecken, die Ermittlung konvexer Hüllen, die Triangulation von Polygonen sowie die Bestimmung von Voronoi-Diagrammen.

[Übersicht]

Aktuelles

  • Die Übung am 09.01.2014 findet ausnahmsweise zu folgender Zeit statt:
    • CAE: 13:15 Uhr bis 14:45 Uhr, Rm. 33/2211
    • INF: 15:45 Uhr bis 17:15 Uhr, Rm. 41/2417
  • Die Vorlesung beginnt am Dienstag, den 07.01.2014.

Termine

Es handelt sich um eine Vorlesung mit drei Vorlesungsstunden und zwei Übungsstunden wöchentlich (3+2 TWS).

Die Vorlesungen finden jeweils statt

dienstags, 15:45 Uhr bis 18:00 Uhr, Rm. 33/0131

Die Übungen finden jeweils statt

CAE+INF: donnerstags, 13:15 Uhr bis 14:45 Uhr, Rm. 33/2211

oder donnerstags, 15:00 Uhr bis 16:30 Uhr, Rm. 33/2211

Für CAE-Studierende wird es eine schriftliche Prüfung geben, welche Teil der Prüfung zum Modul "Algorithmische Geometrie und Robotik" ist. Diese findet voraussichtlich am Dienstag, den 25.03.2014 satt. Für INF-Studierende wird es eine mündliche Prüfung geben. Diese findet voraussichtlich am Mittwoch, den 19.03.2014 statt.

[Übersicht]

Dateien

Vorlesungsfolien sowie Übungsblätter finden Sie in [ILIAS].

[Übersicht]

Literatur

  1. M. de Berg, M. van Kreveld, M. Overmars, O. Schwarzkopf: Computational Geometry: Algorithms and Applications. Third Edition, Springer, Berlin, 2008.
    ISBN 978-3-540-77973-5, DOI 10.1007/978-3-540-77974-2.
    [Online Version] (Innerhalb der Uni kostenlos verfügbar.)
  2. R. Klein: Algorithmische Geometrie, 2. Auflage, Springer, Berlin, Heidelberg, 2005.
    ISBN 3-540-20956-5.
    [Online Version] (Innerhalb der Uni kostenlos verfügbar.)
  3. J. E. Goodman, J. O'Rourke (Hrsg.): Handbook of Discrete and Computational Geometry. Second Edition, Chapman & Hall/CRC, Boca Raton, 2004.
    ISBN 1-58488-301-4.

[Übersicht]