Seminar Algorithmische Geometrie

Das Seminar kann entweder wöchentlich oder als Blockseminar am Ende des Semesters stattfinden. Dies wird nach Absprache mit den Studierenden festgelegt. Am Freitag, den 21. Oktober wird es im Raum O27/531 um 14:00 Uhr eine Vorbesprechung mit Themenvergabe geben. 

Wenn Sie an dem Seminar teilnehmen möchten, aber nicht zur Vorbesprechung kommen können, dann wenden Sie sich bitte per E-Mail an den Veranstalter.

Die Algorithmische Geometrie beschäftigt sich mit geometrisch definierten Problemstellungen, die mit Hilfe von geeigneten kombinatorischen Algorithmen gelöst werden sollen. Grundlegende Objekte sind Punkte, Linien, Polygone etc. Anwendungen für geometrische Algorithmen findet man in den verschiedensten Gebieten, beispielsweise in der Kartographie, der Robotik, im Bereich von Sensornetzen oder im Graphenzeichnen.

Die Inhalte des Seminars orientieren sich an dem Lehrbuch Computational Geometry von M. de Berg et al. Das Seminar ist deshalb sowohl für Studierende der Bachelor- als auch der Masterstudiengänge Informatik und Medieninformatik geeignet.

Mögliche Themen sind:

• Datenstrukturen
• Segmentschnitt
• Polygon Triangulation
• Orthogonale Bereichssuche
• Punktlokalisation
• Voronoi-Diagrammme
• Konvexe Hüllen
• Roboterbewegungsplanung

Literatur:

• M. de Berg, O. Cheong, M. van Kreveld, M. Overmars. Computational Geometry - Algorithms and Applications (3. Auflage). Springer-Verlag, 2008.