Zur
  Seite der TU

Kombinatorische Geometrie II:
Algorithmische Geometrie

Zur Seite des Fachbereichs 3
 

Wintersemester 2000/01

 
LV-Nr.: 0350 L 227


Diese Vorlesung hat im Wintersemester 2000/2001 stattgefunden.

Eine Ankündigung zum Drucken (560K, Postscript).


Dozent: Prof. Günter M. Ziegler
Assistent: Marc Pfetsch

Inhalt

Diese Vorlesung ist der zweite Teil des Studienschwerpunktes "Kombinatorische Geometrie" in den Studiengängen Mathematik, Techno- und Wirtschaftsmathematik.

Grundlegende Probleme und Verfahren der Algorithmischen Geometrie.

Das Gebiet der Algorithmischen Geometrie ("Computational Geometry") hat sich in den letzten 15 Jahren rasant entwickelt. In diesem Gebiet geht es darum, die grundlegenden Objekte der diskreten Geometrie (Punktkonfigurationen, Arrangements von Geraden und Ebenen, Triangulierungen und Unterteilungen, Voronoi-Diagramme etc.) zu verstehen und fundamentale Algorithmen für Ihre Untersuchung und Verwendung zu entwickeln, und auf ihre "Brauchbarkeit" hin zu untersuchen und zu optimieren. Dabei stehen nicht nur theoretische Komplexitätsbetrachtungen im Vordergrund, sondern auch das Bestreben, die Grundalgorithmen für die Anwendung auf (typischerweise) riesige Datensalate in der Praxis "fit" zu machen. Wir werden dabei Anwendungen aus den Bereichen der Computer-Graphik und Bild-Verarbeitung, Robotik, CAD/CAM, geographische Informationssysteme, und der kombinatorischen Optimierung im Auge behalten.

Voraussetzungen:

Etwas Lineare Algebra. C++ (siehe unten).

Literatur


Software

Zusätzlich zu den theoretischen Aufgaben gibt es Programmieraufgaben, die auf dem Paket CGAL (Computational Geometry Algorithms Library) aufbauen. Dieses Bibliothek bietet eine gute Basis an wichtigen grundlegenden Datenstrukturen und ist in C++ geschrieben. Daher müssen die Programme ebenfalls in C++ geschrieben sein.

Übungsblätter

Lösungen



TU Berlin | FB Mathematik | Arbeitsgruppe | FTP HTML 4.0 überprüfen

pfetsch@math.tu-berlin.de zuletzt aktualisiert: 11.10.2002