Vorlesung Algorithmische Geometrie -- TU Berlin, Wintersemester 2004/2005

Aktuelles

• Dienstag, 15.2. nach der Vorlesung Semesterabschlusskaffee im Schwarzen Café (Kantstr. 148)
• Nützliche Programme zur 4. Programmieraufgabe: discrepancy.C und pointlist.C
• Vom 7. bis 11.3.2005: 21st European Workshop on Computational Geometry/Spring School an der Universität Eindhoven

Termine

Inhalt der Vorlesung

Das Gebiet der Algorithmischen Geometrie ("Computational Geometry") hat sich in den letzten 20 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 Computergraphik und Bildverarbeitung, Robotik, CAD/CAM, geographische Informationssysteme, und der kombinatorischen Optimierung im Auge behalten.

In den Übungen sollen einige fundamentale Algorithmen implementiert und mit ihnen experimentiert werden. Dafür werden wir das CGAL-System verwenden.

Sprechstunden

Übungsblätter

Beispielprogramme

• Ein ziemlich nutzloses Programm: polygon.C
• Ein ziemlich nutzloses Programm, das Qt benutzt: qt-polygons.C
• Ein Rahmenprogramm für einen 2D-Konvexe-Hülle-Algorithmus: convex-hull.C

• Überladene Ausgabeoperatoren für STL-Container: stl-ostream.h
  Einfach in das Verzeichnis kopieren (oder verlinken), in dem das Programm liegt und mit #include "stl-ostream.h" einbinden
• Überladener lexikographischer Kleiner-Operator für ebene Punkte: point_cmp_lex_operator.h

• Eine kleine DCEL, die gar nichts tut: dcel-plain.C
• Darstellungsprogramm zur 2. Programmieraufgabe: subdiv-window.C

• Darstellungsprogramm zur 4. Programmieraufgabe: discrepancy.C
• Progrämmchen zum Erstellen von verschiedenen Punktlisten: pointlist.C

Sonstiges

• Hinweise und Beispiele zum Einstieg in CGAL
• Tipps zur Implementierung des Chan-Algorithmus
• Mit balancierten binären Suchbäumen spielen
• Kurzübersicht (ps [80k] oder pdf [24k]) zur CGAL-Implementation einer planaren Unterteilung mittels DCEL
• Voronoiereien:
  • Voronoi-Applet
  • Beachline-Applet
  • Voronoi-Game
• Noch eine Kurzübersicht zu DCELs mit Zusatzinformationen in CGAL: ps [48k] oder pdf [16k]

Literatur

• M. de Berg, M. van Kreveld, M. Overmars, O. Schwarzkopf: Computational Geometry. Algorithms and Applications, Springer-Verlag Heidelberg, Second edition 2000
• Bernd Gärnter: Skript zur Algorithmischen Geometrie (FU Berlin, 1997)
• G. M. Ziegler: Lectures on Polytopes, Graduate Texts in Math. 152, Springer-Verlag, revised edition 1998 (Updates, etc.)

Software

• CGAL
• Bruce Eckel: Thinking in C++
• STL Dokumentation
• Nicolai M. Josuttis: The C++ Standard Library
• Polymake, visualization based on JavaView