Algorithmische Geometrie

Prof. Dr. Stefan Näher

Vorlesung im Hauptstudium über 2 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, ..., 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 des nächsten Nachbarn.

Vorkenntnisse

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

Literatur

Cormen, Leiserson, Rivest: Introduction to Algorithms, Addison-Wesley, 1986
Klein: Algorithmische Geometrie, Oldenbourg, 1997
Mehlhorn, Näher: LEDA - A platform for combinatorial and geometric computing, Cambridge University Press, 1999
O'Rourke: Geometry in C, Cambridge University Press, 1994

Skripten in pdf-Format:
Kujat_Script
Mikus_Script

Termine

Klausurergebnisse

Nachklausur

Sie benötigen zum Bestehen der Klausur 15 Punkte. Die Scheine können ab 22.08. im Sekretariat, Raum H 426, abgeholt werden.

Letzte Änderung 2008-05-27 Maria Gindorf