Institut für Theoretische Informatik, Algorithmik
Suche
Institut für Theoretische Informatik, Algorithmik
Institut für Theoretische Informatik, Algorithmik
Institut für Theoretische Informatik, Algorithmik
Lehre
Wintersemester 2009/2010
Seminar: Algorithmische Geometrie

Seminar: Algorithmische Geometrie

Wintersemester 2009/2010

Allgemeines

Aktuelles

  • LaTeX-Vorlage und nähere Infos zu den Ausarbeitungen auf der Hinweisseite verfügbar.
  • Sobald die finalen korrigierten Ausarbeitungen bei eurem Betreuer vorleigen, kann der Schein ausgestllt werden. Bitte wendet euch dazu an Bastian.

Themenliste

Thema Bearbeiter Betreuer Termin Folien Ausarbeitung Literatur
Geometric Spanners Sinan Ayisik Marcus 24.11. [NS07], Kapitel 9,10
Computing Feed Links Philipp Schneider Martin 24.11. pdf [ABBvKLLSS09], [ABBJdJvKLLSS08]
Voronoi Diagrams Christian Wellenbrock Marcus 1.12. pdf [BCKO08], Kapitel 7
Rectangular Cartograms Thomas Bläsius Martin 1.12. pdf [vKS07]
Proportional Symbol Maps Florian Simon Martin 8.12. pdf [CHvKS09]
PTAS for Euclidean TSP Andreas Schatz Ignaz 8.12. pdf [A98], [A03]
Origami: Tree Method Kai Beskers Bastian 15.12. pdf [DO07], Kapitel 16
Fold & One Straight Cut Jonathan Gräser Bastian 15.12. pdf [DO07], Kapitel 17

Inhalt

Die algorithmische Geometrie beschäftigt sich ganz allgemein mit geometrisch definierten Problemstellungen, die mit Hilfe von geeigneten kombinatorischen Algorithmen gelöst werden sollen. Grundlegende Objekte sind Punkte, Linien, Polygone usw. Anwendungen für geometrische Algorithmen findet man in den verschiedensten Gebieten, beispielsweise in der Kartographie, der Robotik, im Bereich von Sensornetzen oder im Graphenzeichnen. In diesem Seminar werden wir eine Auswahl von aktuellen theoretischen und anwendungsnahen Arbeiten der algorithmischen Geometrie behandeln.

Das Seminar richtet sich an Studierende im Hauptstudium bzw. im Masterstudiengang Informatik und Informationswirtschaft, die Interesse an algorithmischen und geometrischen Fragestellungen haben. Vorkenntnisse aus der Vorlesung Algorithmentechnik werden erwartet. Kenntnisse aus der Vertiefungsvorlesung Graphisch-Geometrische Algorithmen sind hilfreich, jedoch nicht Voraussetzung.

Ablauf

In der Vorbesprechung werden nach einer kurzen Einführung in den Seminarablauf eine Reihe von Themen vorgestellt und unter den Teilnehmern aufgeteilt. Nach drei Wochen der Einarbeitung stellen die Teilnehmer ihr Thema in Form eines Kurzvortrages von etwa 5 Minuten vor. Anschließend folgen an regelmäßigen wöchentlichen Terminen die Hauptvorträge. An jedem Seminartermin finden ein bis zwei Vorträge statt. Ferner ist eine schriftliche Ausarbeitung in LaTeX zu erstellen, die das Thema übersichtlich zusammenfasst.

Beachtet bitte die Hinweise zur Zeitplanung und zur Gestaltung des Vortrags und der Ausarbeitung.

Termine

Datum Thema Folien
20.10. Vorbesprechung [pdf]
10.11. Kurzvorträge
24.11. Vortragstermin
01.12. Vortragstermin
08.12. Vortragstermin
15.12. Vortragstermin
31.01. Ausarbeitung (erste Version)
13.02. Ausarbeitung (finale Version)

Änderungen vorbehalten!

Literatur

Artikel sind größtenteils aus dem Uninetz erreichbar.

[ABBJdJvKLLSS08] B. Aronov, K. Buchin, M. Buchin, B. Jansen, T. de Jong, M. van Krevled, M. Löffler, J. Luo, R. I. Silveira, B. Speckmann. Feed-Links for Network Extensions. In: Proc. 16th International Conference on Advances in Geographic Information Systems (ACM GIS), pp. 308–316, 2008.
[ABBvKLLSS09] B. Aronov, K. Buchin, M. Buchin, M. van Krevled, M. Löffler, J. Luo, R. I. Silveira, B. Speckmann. Connect the Dot: Computing Feed-links with Minimum Dilation. In: Proc. 11th Algorithms and Data Structures Symposium (WADS), pp. 49–60, Lecture Notes in Computer Science 5664, 2009.
[BCKO08] M. de Berg, O. Cheong, M. van Kreveld, M. Overmars. Computational Geometry - Algorithms and Applications (3. Auflage). Springer-Verlag, 2008.
[CHvKS09] S. Cabello, H. Haverkort, M. van Kreveld, B. Speckmann. Algorithmic Aspects of Proportional Symbol Maps. In: Algorithmica, available online, 2009.
[DO07] E. Demaine and J. O'Rourke. Geometric Folding Algorithms - Linkages, Origami, Polyhedra. Cambridge University Press, 2007.
[vKS07] M. van Kreveld and B. Speckmann. On rectangular cartograms. In: Computational Geometry - Theory and Applications 37:175-187, 2007.
[NS07] G. Narasimhan and M. Smid. Geometric Spanner Networks. Cambridge University Press, 2007.
[A98] Sanjeev Arora Polynomial Time Approximation Schemes for Euclidean Traveling Salesman and Other Geometric Problems, Journal of the ACM, vol. 45(5):753–782, 1998
[A03] Sanjeev Arora Approximation schemes for NP-hard geometric optimzation problems: a survey, Math. Program., Ser. B 97:43–69, 2003