Die Vorlesung behandelt den Entwurf, die Analyse und die Implementierung von Algorithmen und Datenstrukturen für geometrische Probleme. Dabei werden grundlegende Vorgehensweisen und Paradigmen, wie ``Teile und Beherrsche'', Plane-Sweep, Dualität, Randomisierung, usw. vorgestellt und auf Problemstellungen aus verschiedenen Bereichen der graphischen Datenverarbeitung angewandt, wie z.B. die Berechnung konvexer Hüllen, Bewegungsplanung für Roboter, Eliminierung von verborgenen Linien und Flächen, Boolesche Operationen auf Polygonen oder die Berechnung der nächsten Nachbarn. Ein zentrales Problem bei der Implementierung von geometrischen Algorithmen ist die Tatsache, dass Computer keine beliebig genauen reellen Zahlen sondern nur Fließkommazahlen zur Verfügung stellen. Die dadurch entstehenden Rundungsfehler können nicht nur zu ungenauen Ergebnissen sondern zum völligen Versagen der Programme führen. Dieses Robustheitsproblem wird in der Vorlesung genauer untersucht und es werden Methoden zu seiner Lösung entwickelt.
Elementare Kentnisse über Datenstrukturen und Algorithmen sind hilfreich sowie Erfahrungen mit einer Programmiersprache wie C, C++ oder Java.
Vorlesung:
Montag, 12-14 Uhr, HS 9
Mittwoch, 12-14 Uhr, HS 6
Übung:
Mittwoch, 16-18 Uhr, V 302