Sprungmarken

Servicenavigation

       

Hauptnavigation

Bereichsnavigation

Proseminar

Algorithmische Geometrie

im Sommersemester 2019



Veranstalter:Jun.-Prof. Dr. Maike Buchin
Termine: Mittwoch12-14 Uhr OH14-304
Beginn: 3.4.2019


[Aktuelles] [Themen] [Zusammenfassung] [Organisatorisches] [Literatur]


Aktuelles

Weitere Informationen sind im Moodle zum Kurs zu finden.
Das Proseminar beginnt in der ersten Vorlesungswoche des Sommersemesters 2019. Die Themen werden am ersten Termin vergeben.


Themen

  • Konvexe Hülle
  • Schnittpunkte von Liniensegmenten
  • Polygone Triangulieren
  • Punktlokalisierung
  • Lineares Programmieren in 2D
  • Bereichsabfragen
  • Fensterabfragen
  • Quadtrees
  • Arrangements und Dualität
  • Voronoi Diagramme
  • Delaunay Triangulierung


Zusammenfassung

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 deren Einsatzgebiete: 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 8-10 Seiten anzufertigen.


Organisatorisches

Der Präsentationskurs zu diesem Proseminar wird extern angeboten. Zu diesem müssen Sie sich über das LSF anmelden.

Die Vortragsthemen werden am ersten Termin vergeben. In den ersten 5 Vorlesungswochen soll eine 8-10 seitige schriftliche Ausarbeitung zum Vortragsthema sowie eine einseitige Zusammenfassung erstellt werden. Die Vorträge beginnen ab der 6. Vorlesungswoche. Jeder Vortrag soll 30 Minuten dauern, plus anschließender Diskussion.

Die Bewertung des Proseminars basiert auf der schriftlichen Ausarbeitung und dem Vortrag.


Literatur

  • [dBCvKO] M. de Berg, O. Cheong, M. van Kreveld, M. Overmars: "Computational Geometry. Algorithms and Application.", Springer, 3rd ed., ISBN: 978-3-540-77973-5
  • [dBvKOS] (erste Ausgabe) M. de Berg, M. van Kreveld, M. Overmars, O. Schwarzkopf: "Computational Geometry. Algorithms and Application.", Springer, 1st ed.
  • [Mt] D. Mount: Computational Geometry - Lecture Notes Fall 2016



Letzte Änderung am 3.4.2019 von M. Buchin