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 weitgehend den Lehrbüchern
M. de Berg, M. van Kreveld, M. Overmars, und O. Schwarzkopf: Computational Geometry, Algorithms and Applications, Springer Verlag, Berlin Heidelberg 1997.und
R. Klein: Algorithmische Geometrie, Addison-Wesley, Bonn, 1997.
Andere Quellen:
H. Edelsbrunner: Algorithms in Combinatorial Geometry, Springer Verlag, Berlin Heidelberg 1987.
J. O'Rourke: Art Gallery Theorems and Algorithms, Oxford University Press, New York, 1987.