MCS 481: Computational Geometry

David Dumas

University of Illinois at Chicago
Spring 2014

The Zone
The zone of a line in a planar arrangement.

General information

Instructor David Dumas (
Lectures MWF 10am in Taft Hall 207
CRN 35483 (undergraduate), 35484 (graduate)
Text Computational Geometry: Algorithms and Applications, 3ed.,
de Berg, Cheong, van Kreveld, and Overmars (Springer-Verlag, 2008)

ISBN-13: 978-3540779735
Office hours Mon & Fri, 2-3pm in SEO 503

Course Materials



In the main textbook unless otherwise noted.
Date (announced) Reading
Mon, Jan 13 Chapters 1 and 2
Mon, Feb 3 Chapter 3
Wed, Feb 12 Chapter 6
Mon, Feb 24 Chapter 7
Wed, Mar 5 Chapter 9
Monday, Mar 17 Chapter 5
Monday, Mar 31 Chapter 8
Monday, Apr 21 Chapter 11
Friday, Apr 25 Paper folding


Problem numbers refer to exercises in the textbook. Notation such as "9.14ac" means parts a and c of problem 9.14, while "9.14" means the entire problem 9.14.
Hwk # Due Problems
0 Fri, Jan 24 Install CGAL and confirm that it is working by compiling and running one of the included example programs. Take a screenshot and email it to
(See sample screenshot and explanation.)
1 Mon, Jan 27 1.4ab, 1.6ab, 1.7ad, 1.9, 1.10bcd
2 Wed, Feb 12 2.2, 2.5, 2.8, 2.11, 2.14 + additional problem
3 Mon, Feb 24 3.3, 3.4, 3.14, 6.1, 6.2
4 Mon, March 10 6.5, 6.6, 7.5, 7.10, 7.11
5 Fri, Mar 21 9.2, 9.5a, 9.9, 9.11, 9.13
6 Mon, Apr 7 5.1(lower bound only), 5.3, 5.4, 5.5ab
7 Mon, Apr 21 8.2, 8.4, 8.11 + additional problems


Project # Due
1 Mon, Feb 10 Convex hull and line segment intersection
Project description: projdesc1.pdf
Source files: projdesc1-files-1.0.tar.gz
2 Fri, Mar 7 Polygons
Project description: projdesc2.pdf
Source files: projdesc2-files-1.0.tar.gz
3 Fri, Apr 4 Voronoi and Delaunay
Project description: projdesc3.pdf
Source files: projdesc3-files-1.0.tar.gz
Final Fri, Apr 11 (proposals)
Fri, May 2 (reports)
Final project details


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 Ubuntu GNU/Linux (e.g. 12.04, where the instructions below were tested), all of the necessary packages can be installed from a regular user account by entering the following commands in a terminal:

sudo apt-get update
sudo apt-get install g++ cmake libcgal-demo
After these commands complete, a compressed archive of the source code of the CGAL example programs is located in /usr/share/doc/libcgal-demo/examples.tar.gz. Thus the following command would decompress the example programs in the current directory (e.g. your home directory):
tar --gzip -xvf /usr/share/doc/libcgal-demo/examples.tar.gz

The exact installation procedure and file locations for other Linux distributions may vary. Check the documentation provided with the CGAL package for your distribution for details.


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

Computational Geometry & Algorithms Resources

Up: Home page of David Dumas