Seminar: Randomisierte Algorithmen in der Algorithmischen Geometrie

• Betreuung: Alexander Wolff, Marc Benkert, Étienne Schramm
• Teilnehmer: Die Zahl der Teilnehmer ist auf 12 begrenzt.

Der Sammelband der Ausarbeitungen liegt vor.

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.

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

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

• NEC ResearchIndex
• Google Scholar
• Digital Bibliography & Library Project
• The Collection of Computer Science Bibliographies

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

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.

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.