Prof. Dr. Christian Sohler |
[Termine] [Themen] [Zusammenfassung] [Literatur]
Wann und wo
Montags, 16:00 - 18:00 Uhr, Otto-Hahn-Str. 14, Raum 304.
Die algorithmische Geometrie befasst sich mit der algorithmischen Behandlung geometrischer Probleme. Geometrische Probleme treten in vielen Anwendungsgebieten auf, beispielsweise in der Computergrafik, in der Optimierung oder im Maschinellen Lernen. Die möglichen Lösungstechniken für geometrische Probleme sind dabei ebenso vielfältig wie ihr Einsatzgebiet: Sie reichen von grundlegenden Verfahren wie Divide-and-Conquer und gierigen Algorithmen über randomisierte Techniken wie randomisierte inkrementelle Konstruktionen und Random Sampling bis hin zu genuin geometrischen Lösungsansätzen wie dem Sweep-Verfahren. Im Zuge der Verwaltung geometrischer Daten für performanten Zugriff, zum Beispiel im Bereich der Computergrafik, sind außerdem spezielle Datenstrukturen nötig.
Das Proseminar verwendet als Grundlage das Buch "Computational Geometry" von de Berg et al.; die Seminarthemen orientieren sich hierbei an den Kapiteln des Buches. Ziel der Vorträge ist dabei nicht die vollständige Behandlung des jeweiligen Kapitels, sondern das für die Seminarteilnehmer verständliche Vorstellen der wesentlichen im gewählten Themengebiet angewendeten Techniken. Zusätzlich zum Vortrag ist eine Ausarbeitung im Umfang von 10-15 Seiten anzufertigen.
| Teilnehmer | Thema | Vortragsgstermin |
|---|---|---|
| Jörg Günnewig | Einführung und konvexe Hüllen in 2 Dimensionen | 12.10.2009 |
| Felix Wegener | Schnitte von Liniensegmenten | 19.10.2009 |
| Mirjam Koch | Triangulierung von Polygonen | 26.10.2009 |
| Jan Ciuper | Geometrische Algorithmen für lineare Programmierung | 2.11.2009 |
| Daniel Hegels | Orthogonale Bereichssuche | 9.11.2009 |
| Adrian Böckenkamp | Lokalisierung von Punkten | 16.11.2009 |
| Tim Debrüggen | Voronoi-Diagramme | 23.11.2009 |
| N.N. | Arrangements und Dualität | ? |
| Nils Schmidt | Delauny-Triangulierung | 30.11.2009 |
| Florian Bellmann | Geometrische Datenstrukturen | 7.12.2009 |
| Simon Dierl | Konvexe Hüllen | 14.12.2009 |
| N.N. | BSP-Bäume | ? |
| N.N. | Bewegungsplanung | ? |
| N.N. | Quad-Trees | ? |
| N.N. | Sichtbarkeitsgraphen | ? |
| N.N. | Simplex-Bereichssuche | ? |