Sprungmarken

Servicenavigation

       

Hauptnavigation

Bereichsnavigation

Seminar

Geometrische Algorithmen und Datenstrukturen

im Sommersemester 2018



Veranstalter:Jun.-Prof. Dr. Maike Buchin
Termine: Montag14-16 UhrOH14-304
Beginn: 9.4.2018


[Aktuelles] [Inhalt] [Themen] [Literatur] [Organisation]


Aktuelles

  • Am 16.7. findet ein zusätzlicher Vortrag um 13:15 Uhr in OH14-104 statt.
  • Der Termin am 4.6. entfällt und alle Termine ab diesem werden um eine Woche verschoben.
  • Das Seminar findet nur an den Terminen statt, an denen ein Vortrag angesetzt ist.
  • Man kann sich für das Seminar per Email an Jun.-Prof. Buchin anmelden.
  • Der erste Besprechungstermin findet in der ersten Vorlesungswoche zum Seminartermin (9.4.2018 um 14:15 Uhr) statt. Dort werden auch die Themen vergeben.


Inhalt

In diesem Seminar beschäftigen wir uns mit Algorithmen und Datenstrukturen für geometrische Probleme. Die Themen werden beim ersten Besprechungstermin am 9.4. vergeben.


Themen

Die Referenzen beziehen sich auf die entsprechenden Kapitel in den weiter unten angegebenen Quellen.
  1. Arrangements 30.4.18
    • Duality, Construction, Zone Theorem [M-7+14,H-23.1]
    • Applications [M-15+28]
  2. Planar Point Location 7.5.18
    • Trapezoidal Maps [M-10]
    • Kirkpatrick [M-25]
  3. Robot Motion Planning 14.5.18
    • Configuration Spaces [M-20]
    • Visibility Graphs [M-29]
  4. Quadtrees 28.5.18
    • Static Quadtrees [H-2.1+2.2]
    • Dynamic Quadtrees [H-2.3+2.4]
  5. Well-seperated pair decomposition 11.6.18
    • Properties and Construction [M-17,H-3.1]
    • Applications [M-18,H-3.2]
  6. Coresets 25.6.18
    • for Directional Width [M-35,H-19]
    • for Extent of Lines [H-20]
  7. Geometric Sampling 2.7.18 [M-19, H-5]
    • Introduction, eps-net and eps-samples
    • Applications and Extensions
  8. Kinetic Data Structures [Leonidas Guibas. Kinetic data structures. Handbook of Data Structures and Applications.]
    Weitere Literatur zu diesen Themen wird am 9.4. vergeben.
    • Heaps; Extent. 9.7.18
    • Convex Hulls; Collision Detection. 16.7.18


Literatur

Wir verwenden folgende zwei Quellen (beide online verfügbar) sowie Originalarbeiten, auf die in diesen verwiesen wird.
  • [M] Lecture Notes CMSC 754 "Computational Geometry" von David Mount
    http://www.cs.umd.edu/class/fall2016/cmsc754/lectures.shtml
  • [H] "Geometric Approximation Algorithms" by Sariel Har-Peled
    http://sarielhp.org/book/
Manche Themen werden ebenfalls in dem Buch "Computational Geometry - Theory and Applications" von Mark de Berg, Otfried Cheong, Marc van Kreveld and Mark Overmars besprochen.

Organisation

Neben einer mündlichen Präsentation im Seminar soll eine ca 10-12 seitige schriftliche Ausarbeitung über das entsprechende Thema bis spätestens drei Wochen nach der Präsentation abgegeben werden. Für die Ausarbeitung empfehle ich Ihnen Latex und für Abbildungen ipe (http://ipe.otfried.org/).

Letzte Änderung am 7.5.2018 von M. Buchin