Algorithmische Geometrie
Prof. Dr. Mark Minas
Wintertrimester 2010
[Ü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.
Aktuelles
Die Übung am Montag, den 15.03.2010 muss leider entfallen. Einen Ersatztermin wird es am Dienstag, den 16.03.2010 von 18:30-20:00 (Rm. 33/2216). Sollten Sie keine Zeit haben, dann wenden Sie sich bitte an Sonja Maier.
Termine
Es handelt sich um eine Vorlesung mit zwei Vorlesungsstunden und zwei Übungsstunden wöchentlich (2+2 TWS).
Die Vorlesungen finden jeweils statt
montags, 8:00 Uhr bis 9:30 Uhr, Rm. 33/0301
Die Übungen finden jeweils statt
12.01.2010: dienstag, 18:30 Uhr bis 20:00 Uhr, Rm. 33/2216
ab 18.01.2010 : montags, 9:45 Uhr bis 11:15 Uhr, Rm. 33/1312
Erster Termin für die Vorlesung ist Montag, 11. Januar 2010. Erster Termin für die Übung ist Dienstag, 12. Januar 2010.
Die schriftliche Prüfung findet voraussichtlich statt am
Montag, 29.03.2010, 8:00 Uhr bis 9:00 Uhr, Rm. 35/1210A
Hinweis zur Klausur: Bitte bringen Sie Bleistift und Lineal zum Zeichnen von Diagrammen mit!
Dateien
Vorlesungsfolien sowie Übungsblätter stehen hier zur Verfügung.
Literatur
M. de Berg, M. van Kreveld, M. Overmars, O. Schwarzkopf: Computational Geometry: 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.