The course covers fundamental concepts and algorithms in computational geometry. Topics covered include: convex hulls, polygon triangulations, range searching, segment intersection, Voronoi diagrams, Delaunay triangulations, motion planning, binary space partitions, geometric polynomial-time approximations schemes, locality-sensitive hashing, metric embeddings and applications.
The course textbooks are Computational geometry by M. de Berg, O. Cheong, M. van Kreveld, M. Overmars, and Lectures on discrete geometry by J. Matousek.
There will be 4-6 homework assignments.
Problem set 1. Posted: Oct 7, 2010, due: Oct 21, 2010.
Problem set 2. Posted: Oct 20, 2010, due: Nov 4, 2010.
Problem set 3. Posted: Nov 8, 2010, due: Nov 18, 2010.
Problem set 4. Posted: Nov 18, 2010, due: Nov 30, 2010.