|
|
Computational Geometry, the theory of geometric
algorithms, has emerged from the field of algorithms theory in the late
70s. It has grown into a recognized discipline with its own journals,
conferences, and a large community of active researchers. The success
of the field as a research discipline can be explained by the mathematical
beauty of its basic problems as well as by its wide range of applications
in computer graphics, geometric information systems, robotics etc.
This course offers an introduction to this rapidly developing field, where
combinatorial and probabilistic (counting) methods play a crucial role.
Some familiarity with combinatorics and probability theory is required.
Topics:
1. Finding the convex hull of a point set
2. Detecting intersections between line segments
3. Triangulating a polygon
4. Linear programming
5. Orthogonal range searching
6. Point location
7. Voronoi diagrams
8. Binary space partitions
9. Robot motion planning
Textbook:
M. de Berg, M. van Kreveld, M. Overmars, O. Schwarzkopf: Computational
Geometry
(2nd ed.), Springer Verlag, Berlin, 2000.
Final Exam: ps,
pdf
|
|