Algorithmische Geometrie (251-0418-00) SS04

Termine

Vorlesung: Dienstag 09-11, IFW B42.

Bernd Gärtner,

IFW B45.1,

Tel: 01-632 70 26,

.

Riko Jacob,

CLW D2,

Tel: 01-632 74 03,

.

Übung: Dienstag 11-12, IFW B42.

Michael Hoffmann,

IFW B47.2,

Tel: 01-632 73 90,

.

Inhalt

In der algorithmischen Geometrie geht es um den Entwurf und die Analyse effizienter Algorithmen für geometrische Probleme. Diese werden in vielen Anwendungen benötigt, z.B. bei der Kurven- und Oberflächenrekonstruktion aus Scanner-Daten, der Visualisierung grosser Datenmengen, oder Ähnlichkeitsabfragen in Datenbanken.

In der Vorlesung werden einige der grundlegenden geometrischen Datenstrukturen behandelt und wichtige Entwurfsparadigmen für geometrische Algorithmen vorgestellt. Die konkrete Anwendbarkeit sowie praktische Aspekte des erlernten Materials werden in den Übungen mit Hilfe der CGAL-Bibliothek diskutiert; CGAL stellt eine grosse Anzahl geometrischer Datenstrukturen und Algorithmen in einer flexiblen Form in C++ zur Verfügung.

Die Vorlesung wird im darauffolgenden Semester mit einem Seminar ergänzt; ferner besteht die Möglichkeit, im Anschluss an Vorlesung oder Seminar eine Semester-, Diplom- oder Masterarbeit im Gebiet der Algorithmischen Geometrie zu schreiben.

Hinweise zur Übung

Auf jeder Übungsserie gibt es eine Aufgabe, die schriftlich zu bearbeiten und zum angegebenen Termin - meist in der Woche darauf - abzugeben ist. Gruppenabgabe wie auch das Einreichen identischer Lösungen sind nicht zulässig.

Unter den Aufgaben werden auch einige Programmieraufgaben (in C++) sein, jedoch keine aufwändigen Projekte, sondern eher kleinere Anpassungen an vorgegebenen Programmgerüsten.

Testatbedingungen

Am Ende der Übungen wird ein Testat vergeben. Das Testat erhält, wer

1. die schriftlichen Aufgaben von allen bis auf zwei Übungsserien sinnvoll, vollständig und selbständig bearbeitet, sowie
2. im Verlaufe des Semesters mindestens drei Aufgaben in der Übungsstunde an der Tafel vorrechnet.

Prüfung

Das Übungstestat ist Voraussetzung für die Zulassung zur mündlichen Prüfung (15 min.). Massgeblich für die Benotung ist allein die Prüfungsleistung.

Literatur

• Mark de Berg, Marc van Kreveld, Mark Overmars, Otfried Schwarzkopf, Computational Geometry: Algorithms and Applications, Springer, 2000.
• Franco P. Preparata, Michael I. Shamos, Computational Geometry: An Introduction, Springer, 1985.
• Bernd's Skript aus Berlin von 1996