Institut für Theoretische Informatik, Algorithmik

Seminar: Randomisierte Algorithmen in der Algorithmischen Geometrie

Sommersemester 2005

Allgemeines

Allgemeines

Der Sammelband der Ausarbeitungen liegt vor.

Inhalt

Im Seminar sollen interessante Methoden der Randomisierung an Beispielen aus der algorithmischen Geometrie an Originalarbeiten erörtert werden. Eine sehr elegante und verblüffend einfache Methode bei der Analyse von Algorithmen ist die Rückwärtsanalyse (siehe [1]), auf die wir immer wieder stoßen werden.

Das Seminar ist besonders für Hörer im Hauptstudium mit Vorkenntnissen in algorithmischer Geometrie und randomisierten Algorithmen geeignet. Voraussetzung für die Teilnahme ist ein gutes Verständnis der „Groß-Oh“-Notation, d.h. man sollte wissen, was es bedeutet, dass eine Sequenz von n Zahlen in O(n log n) Zeit sortiert werden kann (und dass jedes Sortierverfahren, das auf Vergleichen beruht, Omega(n log n) Vergleiche benötigt).

Im Anschluss an den Seminarvortrag muss jeder Teilnehmer eine schriftliche Ausarbeitung seines Vortrags in LaTeX abgeben, die dann gesammelt und eventuell als technischer Bericht herausgegeben werden.

Es wird empfohlen, zeitgleich die Vorlesung Graphisch-geometrische Algorithmen zu hören.

Themen

Teilnehmer Thema Vortragsfolien Referenz
Ignaz Rutter Random Sampling [pdf] [3,4]
Marc Benkert Range Searching [5,6]
Étienne Schramm Delaunay Triangulation [7]

Außerdem finden im Rahmen des Diplomandenseminars folgende Vorträge statt:

Teilnehmer Thema Vortragsfolien
Hui Ma Beschriftung von dichten Punktwolken
Nikolaus Mutsanas Matching mittels geometrischer Objekte [pdf]
Martin Nöllenberg Zeichnen von U-Bahn-Linienplänen

Manche Referenzen können aus dem Netz heruntergeladen werden können. Gute Quellen dafür sind:

Gute Bücher über algorithmische Geometrie sind [8,9,10].

Termine

Das Seminar wird als Blockseminar am Wochenende 18.-19. Juni (Samstag nachmittag bis Sonntag abend) in der Jugendfreizeit- und Bildungsstätte Baerenthal in den Nordvogesen durchgeführt. Deshalb ist die Zahl der Teilnehmer auf maximal 12 begrenzt. Die Kosten für Unterkunft und Vollverpflegung betragen ca. 35 Euro pro Teilnehmer. Die Anfahrt wird nach Möglichkeit durch Fahrgemeinschaften in privaten PKWs organisiert.

Die ersten vier Treffen finden jeweils mittwochs 18:00-19:30 Uhr im SR 301 bzw. nach Vereinbarung statt.

Datum
11.04. Beginn der Vorlesungszeit im Sommersemester 2005
13.04. Themenverteilung
20.04. Wie halte ich einen Seminarvortrag?
28.04. Kurzreferate (jeweils 5-10 Minuten)
18.05. Abgabe der Zusammenfassung (cirka eine Seite)
01.06. Vorstellung der Vortragsfolien beim jeweiligen Betreuer
18.-19.06. Blockseminar in Baerenthal. Abfahrt: Sa, 14:00 Uhr, Fasanengarten 5.
15.07. Ende der Vorlesungszeit im Sommersemester
01.08. Abgabe der Ausarbeitungen (5-10 Seiten)

Literatur

  1. R. Seidel. Backwards Analysis of Randomized Geometric Algorithms. In J. Pach, editor, New Trends in Discrete and Computational Geometry, volume 10 of Algorithms and Combinatorics, pages 37-68. Springer-Verlag, 1993.
  2. Frank Hoffmann and Christian Knauer. Wie gestalte ich einen Seminarvortrag? Freie Universität Berlin, 1998. [pdf]
  3. Otfried Cheong, Alon Efrat, and Sariel Har-Peled. On Finding a Guard that Sees Most and a Shop that Sells Most. In Proc. 15th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'04), pages 1098-1107, Philadelphia, PA, USA, 2004. Society for Industrial and Applied Mathematics.
  4. Otfried Cheong, Alon Efrat, and Sariel Har-Peled. On Finding a Guard that Sees Most and a Shop that Sells Most. Discrete & Computational Geometry, 37(4):545-563, 2007.
  5. David Haussler and Emo Welzl. Epsilon-Nets and Simplex Range Queries. In Proc. 2nd Annual Symposium on Computational Geometry (SoCG'86), pages 61-71, New York, NY, USA, 1986. ACM Press.
  6. David Haussler and Emo Welzl. Epsilon-Nets and Simplex Range Queries. Discrete & Computational Geometry, 2:127-151, 1987.
  7. Kevin Buchin. Incremental Construction along Space-Filling Curves. In Proc. 21st European Workshop on Computational Geometry (EWCG'05), pages 17-20, Eindhoven, 9-11 March 2005.
  8. Ketan Mulmuley. Computational Geometry: An Introduction through Randomized Algorithms. Prentice Hall, Englewood Cliffs, NJ, 1994.
  9. Mark de Berg, Marc van Kreveld, Mark Overmars, and Otfried Schwarzkopf. Computational Geometry: Algorithms and Applications. Springer-Verlag, Berlin, 1997.
  10. Rolf Klein. Algorithmische Geometrie. Addison-Wesley, Bonn, 1997.