Algorithmische Geometrie


Prof. Dr. Stefan Näher

Vorlesung im Hauptstudium über 4 SWS mit Übungen über 2 SWS


Inhalt

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.


Vorkenntnisse

Elementare Kentnisse über Datenstrukturen und Algorithmen sind hilfreich sowie Erfahrungen mit einer Programmiersprache wie C, C++ oder Java.

Termine

Vorlesung:
Montag, 12-14 Uhr, HS 9
Mittwoch, 12-14 Uhr, HS 6
Übung:
Mittwoch, 16-18 Uhr, V 302


Literatur

[CLR90]
T. H. Cormen, C. E. Leiserson und R. L. Rivest.
Introduction to Algorithms.
MIT Press/McGraw-Hill Book Company, 1990

[Kle97]
R. Klein.
Algorithmische Geometrie.
Oldenburg, 1997

[MN99]
K. Mehlhorn und S. Näher.
LEDA, A Platform for Combinatorial and Geometric Computing.
Cambridge University Press, 1999

[OR94]
J. O'Rourke.
Computational Geometry in C.
Cambridge University Press, 1994


Last modified on 2002-09-26
Email: Matthias Bäsken