Inhalte

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.

Organisatorisches

Die Dozenten Laszlo Kozma und Klaus  Kriegel werden die Vorlesung nach Themenblöcken aufteilen. Die Vorlesungen erfolgen als Webex-Meeting (live) und werden aufgezeichnet, bei Kozma auf Englisch, bei Kriegel können die Teilnehmer*innen über Englisch/Deutsch entscheiden.

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.

Webex Lecture information:

Link: https://fu-berlin.webex.com/fu-berlin-en/j.php?MTID=mafc09999bf77d246d35f44ef186eb317

Meeting number: 121 120 7410

Password: F9bpHpdnA53

Nextcloud link:

https://nextcloud.imp.fu-berlin.de/index.php/s/QMbBms5wanR72RQ