Geometrische Algorithmen
Die Algorithmische Geometrie beschäftigt sich mit dem Entwurf und der Analyse von Algorithmen für geometrische Probleme für Objekte wie Punkte, Linien, Polygone, usw. in der Ebene und in höher dimensionalen Räumen. Für viele grundlegende Probleme wurden seit etwa 1970 bis heute neue und zum Teil überraschende Lösungen entwickelt, die für viele Anwendungsgebiete von Bedeutung sind. Typische Anwendungsgebiete, in denen geometrische Probleme eine Rolle spielen, sind die Computer-Graphik, Geographische Informationssysteme, Robotik (insbesondere Bewegungsplanung), CAD und CAM und viele andere. Wir werden in dieser Vorlesung einen von den Anwendungen ausgehenden Überblick über das Gebiet geben und die wichtigsten Algorithmen und Datenstrukturen behandeln. Dazu gehören auch für das Gebiet typische Entwurfsprinzipien wie das Plane-Sweep-Prinzip, geometrisches Divide-and-Conquer, Randomisierung und Dualisierung. Die Vorlesung folgt dem Lehrbuch M. de Berg, M. van Kreveld, M. Overmars, und O. Schwarzkopf: Computational Geometry, Algorithms and Applications, Springer Verlag, Berlin Heidelberg 1997Die Präsentation des Vorlesungsstoffes wird ergänzt um Animationen und Simulationen geometrischer Algorithmen. Daher wird für die Vorlesung der multimediale Hörsaal genutzt. In den Übungen wird u.a. die CGAL-Bibliothek geometrischer Algorithmen eingesetzt. Weil es offenbar für den angekündigten Übungstermin Do 13.30 - 15.30 eine Überschneidung mit einer Kursvorlesung gibt, wird in der ersten Vorlesungsstunde am Di, 13.04.99, ein Ausweichtermin festgelegt. |
