TTIC 31100 / CMSC 39000 Computational geometry

Autumn quarter, 2010.
Intructors: Yury Makarychev, Anastasios Sidiropoulos.
Time: Tue & Thu, 10:30-11:50.
Location: Toyota Technological Institute, 6045 S. Kenwood Ave., Room 530.


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 sets

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.