Seminar Algorithmische Geometrie

Form

Das Seminar ist ein Hauptseminar, das sowohl im Bachelor- als auch im Masterstudiengang belegt werden kann. Es kann entweder wöchentlich oder als Blockseminar am Ende des Semesters stattfinden. Dies wird nach Absprache mit den Studierenden festgelegt.

Inhalt

Die Algorithmische Geometrie beschäftigt sich mit geometrisch definierten Problemstellungen, die mit Hilfe von geeigneten kombinatorischen Algorithmen gelöst werden sollen. Grundlegende Objekte sind Punkte, Linien, Polygone etc. Anwendungen für geometrische Algorithmen findet man in den verschiedensten Gebieten, beispielsweise in der Kartographie, der Robotik, im Bereich von Sensornetzen oder im Graphenzeichnen.

Die Inhalte des Seminars orientieren sich an dem Lehrbuch Computational Geometry von M. de Berg et al. Mögliche Themen sind:

  • Segmentschnitt
  • Lineare Programmierung
  • Polygon Triangulation
  • Orthogonale Bereichssuche
  • Punktlokalisation
  • Voronoi-Diagrammme
  • Delaunay Triangulation
  • Geometrische Datenstrukturen
  • Konvexe Hüllen
  • Unterteilungsbäume
  • Roboterbewegungsplanung
  • Quadtrees

Literatur:

  • M. de Berg, O. Cheong, M. van Kreveld, M. Overmars. Computational Geometry - Algorithms and Applications (3. Auflage). Springer-Verlag, 2008.

Latex: Vorlagen für die

 


Termine

Vorbesprechung mit Themenvergabe:  Freitag, den 17. Oktober 2014 um 14:00 Uhr im Raum 027/531.