Instructor: Ileana Streinu, Room CS232
Office hours: Tue 3:00pm - 4:00pm

Instructor: Oliver Brock, Room CS246
Office hours: Wed 3:00pm - 4:00pm

Computational Geometry

Geometric algorithms lie at the heart of many applications, ranging from computer graphics in games and virtual reality engines to motion planning in robotics or even protein modeling in biology. This graduate course is an introduction to the main techniques from Computational Geometry, such as convex hulls, triangulations, Voronoi diagrams, visibility, art gallery problems, and motion planning. The class will cover theoretical as well as practical aspects of the field. In programming exercises students will be exposed to software packages for geometric computing (such as the LEDA and CGAL libraries, or the application Cinderella). The goal of the class it to enable students to exploit a broad range of algorithmic tools from computational geometry to solve problems in a variety of application areas. Prerequisite: Mathematical maturity. Eligibility: Graduate students only. Others with permission of instructor. 3 credits.

Three homeworks (40%), a take-home midterm (30%), and a final project (30%) will determine the grade.

Textbook:
Computational Geometry - Algorithms and Applications by M. deBerg; M. van Kreveld, M. Overmars, O. Schwarzkopf. Second edition. Springer Verlag, ISBN 3-540-61270-X

The book will be availabe in the Textbook Annex.