Algorithmische Geometrie (Algorithmic Geometry)

VO 111.048 / UE 111.049, Sommersemester 2011

Vorlesungen

Die Vorlesungen zur Algorithmischen Geometrie finden bis inklusive Dienstag 15.3.2011 von 13:00 bis 14:30 und dann von 11:30 bis 13:00 im Dissertantenraum des 8. Stocks, grüner Bereich im Freihaus statt. Die erste Vorlesung wird am 8. März sein. Inhaltlich wird sich die Vorlesung an den Büchern

J. O'Rourke: Computational Geometry in C, Cambridge University Press
M. de Berg, O. Cheong, M. van Kreveld and M. Overmars: Computational Geometry: Algorithms and Applications, Springer-Verlag
J.-D. Boissonnat and M. Yvinec: Algorithmic Geometry, Cambridge University Press.
H. Edelsbrunner: Algorithms in Combinatorial Geometry, Springer
L. J. Guibas und J. Stolfi: Ruler, Compass, and Computer: The Design and Analysis of Geometric Algorithms, SRC 1989

orientieren. Die behandelten Themen umfassen eine Einführung in die Algorithmische Geometrie, Polygonpartitionierungen, Konvexe Hüllen, Voronoi-Diagramme, Delaunay-Triangulierung, Arrangements und Query/Search Datenstrukturen.

Datum	Thema
8. März 2011	Einführung in die Algorithmische Geometrie
15. März 2011	Polygonpartitionierungen: Art Gallery Theorem
22. März 2011	Polygonpartitionierungen: monotone Polygone
29. März 2011	Triangulierung monotoner Polygone, Konvexe Hülle in der Ebene
5. April 2011	Konvexe Hülle im Raum
12. April 2011	Rotating Calipers
3. Mai 2011	Voronoi Diagramme (Algorithmus)
10. Mai 2011	Delaunay Triangulierung
17. Mai 2011	Delaunay Triangulierung: Winkel-Optimalität
24. Mai 2011	Delaunay Triangulierung, Arrangements
31. Mai 2011	Arrangements
7. Juni 2011	Voronoi Diagramme höherer Ordnung, Nächste Nachbarsuche
21. Juni 2011	Vorlesung entfällt
28. Juni 2011	Vorlesungprüfung

Prüfung

Zur mündlichen Vorlesungsprüfung können Sie sich in der Vorlesung oder per E-Mail anmelden.