Graduate Course in Computer Science
Offered by János Pach
Spring term, 2008, Mondays 7:15-9:45 pm
City College, CUNY, Shepard Hall, Room 19
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.
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
M. de Berg, M. van Kreveld, M. Overmars, O. Schwarzkopf: Computational
(2nd ed.), Springer Verlag, Berlin, 2000.
Final Exam: ps,