Princeton University
Computer Science Department

Computer Science 451
Computational Geometry

Bernard Chazelle

Spring 2006

Course Summary

Introduction to basic concepts of geometric computing, illustrating the importance of this new field for computer graphics, solid modeling, robotics, databases, pattern recognition, and statistical analysis. Algorithms for geometric problems. Fundamental techniques, e.g., convex hulls, Voronoi diagrams, intersection problems, multidimensional searching. Prerequisites: COS 226 and 341, or equivalent.

Administrative Information

Lectures: TTH 1500-1620, Room: 102

Professor: Bernard Chazelle - 404 CS Building - 258-5380 chazelle@cs.princeton.edu

Undergraduate Coordinator: Donna O'Leary - 410 CS Building - 258-1746 doleary@cs.princeton.edu

Teaching Assistants: TBA

Textbooks: Computational Geometry, Algorithms and Applications by de Berg, M., van Kreveld, M., Overmars, M., Schwarzkopf, O., Springer-Verlag, 1997.

A good, but more elementary and narrowly-focused, text is Computational Geometry in C by J. O'Rourke, Cambridge Univ. Press, 2nd ed., 2001. Two other good books, less comprehensive but more advanced, are Algorithms in Combinatorial Geometry, by H. Edelsbrunner, Springer-Verlag, 1987, and Multidimensional Searching and Computational Geometry by K. Mehlhorn, Springer-Verlag, 1984. The classic, Computational Geometry: An Introduction, by F.P. Preparata and M.I. Shamos, Springer-Verlag, 1985, is still good but is showing signs of age.

Assignment 1: Due March 14, 2006.

Assignment 2: Due April 4, 2006.

Assignment 3: Due April 18, 2006.

Final Project: Due May 16, 2006.