Effiziente Algorithmen für geometrische Probleme, z.B. Finden der konvexen Hülle einer Punktmenge, Voronoi-Diagramme, Delaunay-Triangulierung, geometrische Datenstrukturen, etwa zum Finden eines Punktes in einer ebenen Unterteilung. Das Gebiet hat Anwendungen in Computer-Graphik, Muster- und Formerkennung, geographischen Informationssystemen, CAD usw.

Literatur

• M. de Berg, O. Cheong, M. van Kreveld, M. Overmars. Computational Geometry: Algorithms and Applications. Springer-Verlag Berlin, 2008.
• R. Klein. Algorithmische Geometrie. Addison-Wesley, 1997.
• J.-D. Boissonnat, M. Yvinec. Algorithmic Geometry. Cambridge University Press, 1998.
• F.P. Preparata, M.I. Shamos. Computational Geometry: An Introduction. Springer-Verlag New York, 1985.
• K. Mehlhorn. Data Structures and Algorithms, Vol. 3: Multi-dimensional Searching and Computational Geometry. Springer-Verlag Berlin, 1984.

Zusätzliche Informationen

Empfohlene Vorkenntnisse: "Höhere Algorithmik" oder verwandte Veranstaltungen.

Da es sich um eines der Hauptarbeitsgebiete der AG Theoretische Informatik handelt, ist ein Besuch für alle ratsam, die bei einem Dozenten dieser Gruppe eine Bachelor- oder Masterarbeit anfertigen wollen. Solche Arbeiten können im Anschluss an die Vorlesung vergeben werden.