RUB » LMI » Lehre » Algorithmische Geometrie WS16

Algorithmische Geometrie Winter 2016/2017

LVR-Nr: 150 341
Veranstaltung: Algorithmische Geometrie
2 std.
NA 1/64 Fr 8.30-10.00
Dozentin: Maike Buchin
Übungen: Stef Sijben
2 Std.
NA 1/64 Do 10.00 - 12.00
Die erste Übung findet am 27.10. statt.

News

  • Am Fr 10.2.17 fällt die Vorlesung aus, die Übung am 9.2.17 findet statt.
  • Am Do 22.12.16 findet um 8:30 Uhr eine Vorlesung in NA 1/64 statt.
  • In der Woche vom 7.-11.11.16 fallen Vorlesung und Übung aus.

Kommentar

Die Algorithmische Geometrie beschäftigt sich mit dem Entwurf und der Analyse von Algorithmen und Datenstrukturen für geometrische Probleme. In der Vorlesung werden zunächst folgende grundlegende Probleme betrachtet: Wie berechnet man die konvexe Hülle einer Punktmenge? Wie findet man die Schnittpunkte einer Menge von Strecken? Wie trianguliert man ein Polygon? Des Weiteren werden geometrische Datenstrukturen wie Range-trees, Voronoi-Diagramme, Delaunay-Triangulierungen, Arrangements, und Quadtrees betrachtet. Dabei werden verschiedene Typen von Algorithmen verwendet: inkrementell, teile-und-herrsche, und sweep. Insbesondere betrachten wir randomisierte Algorithmen.

Voraussetzungen

Es werden grundlegende Kenntnisse über Algorithmen und Datenstrukturen erwartet, sowie grundlegende Kenntnisse der Stochastik.

Literatur

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).

Materialien

Die Materialien werden im zugehörigen Moodle-Kurs veröffentlicht.

Prüfungen

Die Prüfungsleistung zum Modul Algorithmische Geometrie ist in Form einer mündlichen Prüfung zu erbringen.

Als Termine stehen Mi 22.2.17 und Mi 19.4.17 zur Auswahl.

Die Prüfungsanmeldung erfolgt nach den Regeln des für Sie zuständigen Prüfungsamtes.

Bitte lassen Sie sich vor der Anmeldung zur Prüfung eine Uhrzeit von Stef Sijben geben.

Kontakt