Simple geometric objects such as points, lines, planes and spheres are the basic building blocks for modeling the complex shapes and phenomena of the real world. Despite their apparent simplicity, they raise challenging combinatorial and algorithmic problems that are fundamental to many applied fields, such as computer graphics, robotics, visualization, molecular biology, and databases. This course introduces the fundamental concepts and algorithmic techniques of computational geometry for dealing with these problems. This is a graduate level course, and students are expected to know the basic concepts of algorithm analysis (asymptotic notation, worst-case analysis) and data structures (linked lists, trees, priority queues).
A good quick overview of the topic can be found at Geometry Algorithms Overview.
The final grade will be based on the following components:
(1) homework assignments (30%),
(2) a midterm exam (20%),
(3) presentation and written report on a research paper (30%), and
(4) an oral exam about the chosen research paper (20%).
The homework assignments and the midterm exam will be exercises in algorithm design and analysis. For the paper presentation component, each student is expected to choose a computational geometry research publication from this Reading List read and thoroughly understand it, give a short (15-20 minutes) presentation to the class, and write a 10 page report, explaining the main theoretical insights of the paper in your own words.
The textbook for the course is Computational Geometry, by de Berg, van Kreveld, Overmars, and Schwarzkopf. This is a fairly well-written introductory textbook. In addition, my own lecture slides will be available below. However, keep in mind that these slides are not an excuse to skip lectures. The lectures typically involve worked examples and interaction in the form of questions and answers, which can't be captured in the slides.
The Midterm will be on Oct 23.