MCS 481: Computational Geometry

David Dumas

University of Illinois at Chicago
Spring 2012

The Voronoi diagram of a pseudorandom perturbation of the square lattice (selected cells shaded).

General information

Instructor David Dumas (
Office hours Wed and Fri 11am-12pm in SEO 503
CRN 31103 (undergraduate), 31104 (graduate)
Lectures MWF 2:00 - 2:50pm in Taft Hall 219
Text de Berg, Cheong, van Kreveld, and Overmars.  Computational Geometry: Algorithms and Applications, 3ed. Springer-Verlag, 2008.
ISBN-13: 978-3540779735   (compare prices and availability at several booksellers)

Course Materials



CGAL and its dependencies are available as binary packages for some operating systems, including several versions of GNU/Linux, and this is often the easiest way to install these programs. For example, on recent versions of Debian GNU/Linux, all of the necessary packages can be installed with the command:
apt-get install g++ cmake libcgal-demo


Your course grade will be determined on the following basis:
Homework 30%
Projects 30%
Final project 40%


Up: Home page of David Dumas