Institut für Theoretische Informatik, Algorithmik

Seminar: Konstruktion und Analyse geometrischer Graphen

Sommersemester 2003

Allgemeines

Ankündigung

Geometrische Netzwerke sind das Rückgrat bei der Modellierung von Verkehrs-, Waren- und Informationsströmen - ob in der Eisenbahnnetzplanung, dem VLSI-Layout oder der Analyse des Internets.

Im Seminar wollen wir einige interessante Themen aus dem Gebiet der geometrischen Netzwerke herausgreifen und in Vorträgen analysieren. Jeder Vortrag soll cirka eine Stunde dauern und kann von zwei StudentInnen gemeinsam voorbereitet und gehalten werden. Es wird Wert auf gut strukturierte, verständliche Vorträge gelegt. Da 12 Termine zur Verfügung stehen, ist die Zahl der TeilnehmerInnen auf 24 beschränkt.

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).

Bitte bei der Vortrags- und Folienvorbereitung unbedingt die Tipps in [1] und [2] beachten! Die Vortragsfolien müssen mindestens eine Woche vor dem Vortrag dem jeweiligen Betreuer vorgelegt werden.

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.

Vortragsthemen

Geometrische aufspannende Bäume minimalen Durchmessers [3][4][5]
Well-Separated Pair Decomposition [6]
Geometrische aufspannende Bäume minimalen Gewichts [7][8][9]
Konstruktion Euklidischer Spanner [10][11][12][13]
Analyse Euklidischer Spanner [14]
Rektilineare Steinerbäume [15][16][17][18]
Minimale Manhattan-Netzwerke [19][20]

Ein Ordner mit allen Artikeln (insbesondere mit denen, die nicht online verfügbar sind), wird im Sekretariat von Frau Heck, Zimmer 321, zur Einsicht bereitgestellt.

Bitte beachten Sie, dass viele der Referenzen (auch von denen, auf die Ihre Artikel verweisen) aus dem Netz heruntergeladen werden können. Gute Quellen dafür sind:

Die Literaturliste und die Themenübersicht gibt's auch als Postscript-Datein.

Gute Bücher über algorithmische Geometrie sind [21][22].

Termine

13. Mai Kurzreferate
20. Mai - fällt aus -
27. Mai Sebastian Kring MDST [3]
3. Juni Lothar Kunz RST [15] Vortragsfolien [pdf,ppt]
10. Juni Csaba Megyeri RST [16][17]
17. Juni Khoder El-Zein MST [7] Vortragsfolien [pdf]
24. Juni Jiwei Wang theta-Graph [10] Vortragsfolien [pdf,ppt]
1. Juli Michael Kuperberg WSPD [6]
6. Juli Hui Ma Spanner [11][12]
15. Juli
22. Juli

Literatur

  1. Simon L. Peyton Jones, John Hughes, and John Launchbury. How to Give a Good Research Talk. ACM SIGPLAN Notices, 28(11):9-12, November 1993.
  2. Frank Hoffmann and Christian Knauer. Wie gestalte ich einen Seminarvortrag? Freie Universität Berlin, 1998.
  3. Jan-Ming Ho, D. T. Lee, Chia-Hsiang Chang, and C. K. Wong. Minimum Diameter Spanning Trees and Related Problems. SIAM Journal on Computing, 20(5):987-997, October 1991.
  4. Refael Hassin and Arie Tamir. On the Minimum Diameter Spanning Tree Problem. Information Processing Letters, 53(2):109-111, 1995.
  5. Timothy M. Chan. Semi-Online Maintenance of Geometric Optima and Measures. In Proc. 13th ACM-SIAM Symposium on Discrete Algorithms (SODA'02), pages 474-483, San Francisco, 6-8 January 2002.
  6. Paul B. Callahan and S. Rao Kosaraju. A Decomposition of Multidimensional Point Sets with Applications to k-Nearest-Neighbors and n-Body Potential Fields. Journal of the ACM, 42(1):67-90, January 1995.
  7. Pankaj K. Agarwal, Herbert Edelsbrunner, Otfried Schwarzkopf, and Emo Welzl. Euclidean minimum spanning trees and bichromatic closest pairs. Discrete Comput. Geom., 6(5):407-422, 1991.
  8. Paul B. Callahan and S. Rao Kosaraju. Faster Algorithms for Some Geometric Graph Problems in Higher Dimensions. In Proc. 4th ACM-SIAM Sympos. on Discrete Algorithms (SODA'93), pages 291-300, 1993.
  9. Giri Narasimhan, Jianlin Zhu, and Martin Zachariasen. Experiments with Computing Geometric Minimum Spanning Trees. In Proc. 2nd Workshop on Algorithm Engineering and Experiments (ALENEX'00), pages 183-196, San Francisco, January 2000.
  10. J. Mark Keil. Approximating the Complete Euclidean Graph. In R. Karlsson and A. Lingas, editors, Proc. First Scandinavian Workshop on Algorithm Theory (SWAT'88), volume 318 of Lecture Notes in Computer Science, pages 208-213, Halmstad, Sweden, 5-8 July 1988. Springer-Verlag.
  11. Gautam Das, Paul J. Heffernan, and Giri Narasimhan. Optimally Sparse Spanners in 3-Dimensional Euclidean Space. In ACM-SIGACT ACM-SIGGRAPH, editor, Proc. 9th Annual Symposium on Computational Geometry (SoCG'93), pages 53-62, San Diego, CA, May 1993. ACM Press.
  12. Sunil Arya, Gautam Das, David M. Mount, Jeffrey S. Salowe, and Michiel Smid. Euclidean Spanners: Short, Thin, and Lanky. In Proc. 27th Annu. ACM Sympos. Theory Comput. (STOC'95), pages 489-498, Las Vegas, 29 May-1 June 1995.
  13. David Eppstein. Spanning Trees and Spanners. In Jörg-Rüdiger Sack and Jorge Urrutia, editors, Handbook of Computational Geometry, pages 425-461. Elsevier Science Publishers B.V. North-Holland, Amsterdam, 2000.
  14. Giri Narasimhan and Michiel Smid. Approximating the Stretch Factor of Euclidean Graphs. SIAM J. Comput., 30:978-989, 2000.
  15. Michael J. Garey and David S. Johnson. The rectilinear Steiner tree problem is NP-complete. SIAM Journal of Applied Mathematics, 6:826-834, 1977.
  16. Joseph L. Ganley and James P. Cohoon. Optimal Rectilinear Steiner Minimal Trees in O(n2·2.62n) Time. Proc. Sixth Canadian Conference on Computation Geometry, pages 308-313, 1994.
  17. Joseph L. Ganley. Computing optimal rectilinear Steiner trees: A survey and experimental evaluation. Discrete Applied Mathematics, 89:161-171, 1999.
  18. Hans Jürgen Prömel and Angelika Steger. The Steiner Tree Problem - A Tour through Graphs, Algorithms, and Complexity. Vieweg Verlag, 2002.
  19. Joachim Gudmundsson, Christos Levcopoulos, and Giri Narasimhan. Approximating a Minimum Manhattan Network. Nordic J. Comput., 8:219-232, 2001.
  20. Ryo Kato, Keiko Imai, and Takao Asano. An Improved Algorithm for the Minimum Manhattan Network Problem. In Prosenjit Bose and Pat Morin, editors, Proc. 13th Annual International Symposium on Algorithms and Computation (ISAAC'02), volume 2518 of Lecture Notes in Computer Science, pages 344-356, Vancouver, 20-23 November 2002. Springer-Verlag.
  21. Mark de Berg, Marc van Kreveld, Mark Overmars, and Otfried Schwarzkopf. Computational Geometry: Algorithms and Applications. Springer-Verlag, Berlin, 1997.
  22. Rolf Klein. Algorithmische Geometrie. Addison-Wesley, Bonn, 1997.