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

VorlesungMontag08 - 10 hHZ 203
ÜbungDienstag12 - 14 hH 11

Klausurergebnisse

Matrikel-Nr.Punkte
754 23734
697 29134
651 75828
802 19025
652 29524
773 64523
676 93723
708 48322
842 65520
914 52619
833 98817
719 26216
746 33215
843 15515
757 2149
839 5898
774 1212

Nachklausur

Matrikel-Nr.Punkte
643 48836

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