Algorithmische Geometrie
Prof. Dr. Mark Minas
Wintertrimester 2007
[Ü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.
Termine
Es handelt sich um eine Vorlesung mit zwei Vorlesungsstunden und zwei Übungsstunden wöchentlich (2+2 TWS).
Die Vorlesungen finden jeweils statt
dienstags, 14:15 Uhr bis 15:45 Uhr in Raum 33/1101
Die Übungen finden jeweils statt
montags, 11:00 Uhr bis 12:30 Uhr in Raum 33/0401
Erster Termin für die Vorlesung ist Dienstag, 9. Januar. Erster Termin für die Übung ist Montag, 15. Januar.
Für Fasching wird folgende Regelung getroffen: die Vorlesung von Dienstag nachmittag (20.02.) wird auf die Übungszeit am Montag (19.02.) verschoben (dann entsprechend in 33/0401 um 11:00 Uhr). Die Übung wird dann am Dienstag (20.02.) gehalten in 41/2407 um 10:00 Uhr.
Dateien
Vorlesungsfolien sowie Übungsblätter stehen hier zur Verfügung.
Literatur
M. de Berg, M. van Kreveld, M. Overmars, O. Schwarzkopf: Computational Theory: Algorithms and Applications. Second Edition, Springer, Berlin, 2000. ISBN 3-540-65620-0.
R. Klein: Algorithmische Geometrie, 2. Auflage, Springer, Berlin, Heidelberg, 2005. ISBN 3-540-20956-5.
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.