Computational Geometry

Graduate Course in Computer Science and Mathematics
Offered by János Pach
City College, CUNY

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

Textbook: M. de Berg, M. van Kreveld, M. Overmars, O. Schwarzkopf: Computational Geometry
(2nd ed.), Springer Verlag, Berlin, 2000.

Final Exam: ps, pdf