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 das Hauptarbeitsgebiet 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.