LEA

Hauptseminar: Algorithmische Geometrie

  • Leitung:
    Riko Jacob, PhD,
    Dr. Hanjo Täubig
  • Bereich:
    2 SWS Hauptseminar im Bereich Informatik III (Theoretische Informatik)
  • Zeit und Ort:
    Donnerstag, 14:15 - 15:45, MI 03.11.018
  • Schein:
    Einen Seminarschein erhält, wer einen Vortrag gehalten und regelmäßig am Seminar teilgenommen hat.
  • Hörerkreis:
    Studierende im Hauptstudium der Informatik
    Studierende mit Nebenfach Informatik
  • Voraussetzungen:
    Voraussetzung für die Teilnahme am Hauptseminar sind neben Interesse an Algorithmen, Komplexität und mathematischen Fragestellungen auch Englischkenntnisse, die ausreichend für die Bearbeitung der ausschließlich englischsprachigen Literatur sein sollen.
  • Zusammenfassung:
  • Vorträge:
    Datum Vortragender Titel Betreuer
    26.06.2008 Nicolas Heuser Point Location Riko Jacob
    10.07.2008 Jonathan Will Orthogonal Range Searching Johannes Nowak
    17.07.2008 Tobias Lieber Simplex Range Searching Dmytro Chibisov
  • Inhalt:
    1. Line Segment Intersection
    2. Polygon Triangulation
    3. Linear Programming
    4. Orthogonal Range Searching
    5. Point Location
    6. Voronoi Diagrams
    7. Arrangements and Duality
    8. Delaunay Triangulations
    9. More Geometric Data Structures
    10. Convex Hulls
    11. Binary Space Partitions
    12. Robot Motion Planning
    13. Quadtrees
    14. Visibility Graphs
    15. Simplex Range Searching
  • Literatur:
    Die Vortragsthemen basieren auf den Kapiteln des folgenden Buchs:
    • M. de Berg, M. van Kreveld, M. Overmars, O. Schwarzkopf:
      Computational Geometry,
      Second Edition, Springer, 2000.
  • Ablauf der Vorbereitung:

    Der Vortrag und die Ausarbeitung müssen mit dem Betreuer abgesprochen werden. Hierzu sind nachfolgende Terminvorgaben bindend (soweit nicht anders mit dem Betreuer abgestimmt). Werden die Termine nicht eingehalten, führt dies zur Streichung des Vortrags und zum Nichtbestehen des Seminars:
    bis 5 Wochen vor dem Vortrag erstes Treffen mit dem Betreuer (vor dem Treffen ist die Literatur bereits zu lesen); der genaue Termin ist bei den Vortragsterminen angegeben;
    bis 3 Wochen vor dem Vortrag Gliederung des Vortrags und der Ausarbeitung mit dem Betreuer besprechen;
    bis 1 Woche vor dem Vortrag Probevortrag vor den Betreuer; fertige Folien und vollständige erste Version der Ausarbeitung mit dem Betreuer abstimmen;
    bis 2 Wochen nach dem Vortrag fertige Ausarbeitung abgeben.
  • Hinweise zur Anfertigung einer Seminararbeit:
    • Alle Ausarbeitungen sollen vorzugsweise mit dem Textsatzsystem LaTeX erstellt werden. Hierzu sind folgende Richtlinien zu beachten:
    • Der folgende Rahmen ist zu verwenden (seminararbeit.tex). Dabei dürfen die Seitengröße und der Font nicht verändert werden.
    • Ein Beispiel kann in der Datei example.tex gefunden werden (das Bild example.eps wird eingebunden)
    • Die Ausarbeitung soll auf die verwendete Literatur verweisen, diese Literatur ist mit BibTeX zu verwalten und in einer eigenen Datei zu speichern (hier die zum Beispiel gehörende Datei: example.bib).
    • Bei Fragen zu LaTeX sei einerseits auf die folgenden Links hingewiesen, ferner kann auch der Betreuer um Hilfestellungen bzw. Literaturangaben gebeten werden:
    • Eine TeX-Implementation unter Windows finden Sie hier.
  • Hinweise zur Gestaltung der Vorträge:
    Wer seine Folien mit LaTeX erstellen möchte findet hier einige Hinweise (einschließlich Rahmen-Datei als Vorlage)