Computational Geometry
Summer Term 2010
Times and places
Carsten Schultz: Mo 8.30-10, 10-12, MA 841.
Tutorials by Bernd Gonska:
Fri 8-10, MA 549.
Nachbesprechung am Mittwoch, 14. 7. um 18:00 im Schleusenkrug.
Exercises
Everyting related to the exercises can be found here.
Overview
In dieser Vorlesung wird eine Einführung in die algorithmische Geometrie ("computational geometry") gegeben. Ausgangspunkt dieses Gebiets ist es, algorithmische Probleme auf den grundlegenden Objekten der diskreten Geometrie (Punktkonfigurationen, Polytope, Arrangements von Geraden und Ebenen, Triangulierungen und Unterteilungen, Voronoi-Diagramme, etc.) zu verstehen und effiziente Algorithmen für ihre Behandlung zu entwickeln.
Topics covered
- Convex Hull in 2 dimensions
- [2; 2]
- Minimal distance pair of points
- [2; 3.1]
- Convex Sets
- [3; 2-3]
- Convex hull in n dimensions
- [3; 5]
- Linear Optimization
- [3; 4]
- Doubly connected edge lists
- [1; 2.2]
- Voronoi diagrams
- [3; 6], [1; 7.1,7.2], [1; 11.5], [2; 3.2]
- Delone subdivisions
- [3; 7], [1; 9]. [2;3.3]
- Convex hull in 3 dimensions
- [1; 11]
- Configuration Space Scheme for Randomized Incremental Algorithms
- [1;9.5]
- Trapezoidal maps
- [1; 6], [2; 4.2]
- Line arrangements
- [1; 8.3], [2; 4.3]
- Intersections of line segments
- [1; 2]
- Range trees
- [1; 5.3-5.6], [2; 5.2]
- Triangulating polygons
- [1; 3]
- Minimal enclosing disc
- [1; 4.7], [2; 6.1]
- Curve reconstruction
- [3; 11]
Bibliography
- M. de Berg, M. van Kreveld, M. Overmars, O. Schwarzkopf:
Computational Geometry. Algorithms and Applications,
Springer-Verlag Heidelberg, Second edition 2000
- Bernd Gärnter:
Skript zur Algorithmischen Geometrie
(FU Berlin, 1997)
-
M. Joswig und T. Theobald, Algorithmische Geometrie, Vieweg, Wiesbaden, 2008.
