====== Modul Geometrische Algorithmen  (SoSe 2022) ======

| Veranstalter | Prof. Dr. Kevin Buchin |
| Modul          | Diplom, Master INF-MSc-602 (Informatik, Angewandte Informatik) | 
| Veranstaltungsart    | VO 2 + UE 2                 |
| Veranstaltungsnummer | [[https://www.lsf.tu-dortmund.de/qisserver/rds?state=verpublish&status=init&vmfile=no&publishid=267717&moduleCall=webInfo&publishConfFile=webInfo&publishSubDir=veranstaltung|042515]]                   |
| Vorlesungsseite | [[https://moodle.tu-dortmund.de/course/view.php?id=34069|moodle]]|

===== Inhalt und Themen =====
Geometrische Algorithmen umfasssen den Entwurf und die Analyse von Algorithmen und Datenstrukturen für geometrische Probleme. In der Vorlesung werden zunächst einige grundlegende Probleme betrachtet: Das Berechnen der konvexen Hülle einer Punktmenge, der Schnittpunkte einer Menge von Strecken, oder einer Triangulierung eines einfachen Polygons. Anschließend sehen wir Algorithmen zum Berechnen bekannter geometrische Strukturen, wie Voronoi-Diagramme, Delaunay-Triangulierungen und Arrangements. Ebenfalls betrachten wir Datenstrukturen für effiziente Anfragen auf geometrischen Daten, wie Range-trees, kd-Bäume und Quadtrees. Dabei kommen vor allem drei Arten von Algorithmen zum Einsatz: inkrementell, teile-und-herrsche, und sweep. Manche von diesen treten als randomisierte Algorithmen auf. 

Als Vorkenntnisse wird die Vorlesung "Algorithmen und Datenstrukturen" oder vergleichbare Kenntnisse erwartet.

===== Ort und Zeit =====

  * Vorlesung + Übung
    * Montag, 10:15-12:00 Uhr, [[https://www.lsf.tu-dortmund.de/qisserver/rds?state=verpublish&status=init&vmfile=no&moduleCall=webInfo&publishConfFile=webInfoRaum&publishSubDir=raum&keep=y&raum.rgid=4035|OH 14 Raum 104]], Vorlesung
    * Mittwoch, 10:15-12:00 Uhr, [[https://www.lsf.tu-dortmund.de/qisserver/rds?state=verpublish&status=init&vmfile=no&moduleCall=webInfo&publishConfFile=webInfoRaum&publishSubDir=raum&keep=y&raum.rgid=4035|OH 14 Raum 104]], Übung
  * Beginn der Vorlesungen: tba

===== Prüfungen =====

  * Prüfungen (s. Modulbeschreibung sowie Folien der ersten Vorlesung): 
    * mündlich 
    * aktive Teilnahme (inkl. Präsentation eigener Lösungen)


===== Materialien =====

  * Vorlesungsfolien
  * Die Vorlesung orientiert sich im Wesentlichen an dem Buch "Computational Geometry: Algorithms and Applications", von Mark de Berg, Otfried Cheong, Marc van Kreveld, und Mark Overmars (3. Auflage, 2008, Springer).