Algorithmische Geometrie (KG II)

Wintersemester 2008/09
Prof. Stefan Felsner

LV-Nr.: 0230 L 227
Do 10-12, MA 851
Fr 10-12, MA 851

This course is offered in the context of Berlin Mathematical School and thus optionally taught in English.

Aktuell:

Diese Seite ist noch in Arbeit

Inhalt:

Als Anfang der Algorithmischen Geometrie ("Computational Geometry") gilt das Erscheinen des Buchs von Preparata, Shamos 1985. Seitdem hat sich das Gebiet rasant entwickelt. Ein Höhepunkt war Ende der 90er Jahre als einige Bücher erschienen die das ganze Gebiet abdeckten. Der damalige Stand, die klassische Algorithmischen Geometrie, ist das Hauptthema der Vorlesung. Es umfasst das Studium von grundlegenden Objekten der diskreten Geometrie (Punktkonfigurationen, Arrangements von Geraden und Ebenen, Triangulierungen und Unterteilungen, Voronoi-Diagramme etc.), sowie die Bereitstellung von Techniken und Datenstrukturen zum Entwurf und der Analyse von geometrischen Algorithmen (Randomisierte Konstruktion, Sweep, Baumstrukturen etc.).

In der Vorlesung wird die klassische Algorithmischen Geometrie etwa zwei Drittel ausmachen. Ergänzend werden aktuelle Arbeiten aus dem Gebiet behandelt.
Quellen hierfür sind die großen jährlich stattfindenden CG Konferenzen und internationale Zeitschriften, insbesondere:

Zielgruppe:

Studentinnen und Studenten der Mathematik, Techno- und Wirtschaftsmathematik (ab 4. Semester) und der Informatik (Hauptstudium).
Diese Vorlesung ist Teil des Studienschwerpunkts Kombinatorische Geometrie

Übungen:

Termin: Fr, 14-16
Raum: MA 648

Übungsleitung Daniel Heldt

Scheinbedingungen

In Absprache

Übungsblätter

Die Übungsblätter werden auf der Website als pdf-Datei veröffentlicht.
  1. Übungsblatt [pdf]
  2. Übungsblatt [pdf], [Point.java], [KonvexHull.java]
  3. Übungsblatt [pdf]
  4. Übungsblatt [pdf]
  5. Übungsblatt [pdf]
  6. Übungsblatt [pdf]
  7. Übungsblatt [pdf]
  8. Übungsblatt [pdf]
  9. Übungsblatt [pdf]
  10. Übungsblatt [pdf]
  11. Übungsblatt [pdf]
  12. Übungsblatt [pdf]
  13. Übungsblatt [pdf]

Literatur: Computational Geometry Textbooks
Zuletzt bearbeitet: 30. Januar 2009