Spring 2013: Computational Geometry, 22C:196:001


The course meets 9.30--10.45 am Tuesday and Thursday at 218 MLH (MacLean).


Kasturi Varadarajan, 101D MacLean Hall, Phone: 335-0732, email:firstname-lastname@uiowa.edu.

Office hours: 3.00 -- 4.30 Monday, and 2.00 -- 3.30 Wed.

What this Course is About

The first part of the course will focus on the following topics, and we will spend approximately one week per topic. A good reference for this is Computational Geometry, Algorithms and Applications, by de Berg, Cheong, van Kreveld, and Overmars. Our library has an electronic subscription (and hard copy subscriptions as well, if you can grab them). The second part will cover the following topics: References will be posted subsequently.


We will assume effectively an exposure to an undergraduate data structures course, so that when we talk about algorithms, you are comfortable at seeing how they might translate into programs. This also means you have seen the mechanics of analyzing the running time of simple algorithms. It helps to have also been exposed to an undergraduate algorithms course.


Grading will be based on homeworks (40 percent), a midterm (25 percent), and a final (35 percent). The homeworks will either be problem sets or programming assignments.

The policy on late homeworks is that you have a quota of three days for the entire semester that you may use for late submissions. So for example, there will be no penalty if you submit the third homework a day late, the fifth two days late, and the rest of the homeworks on time. Once you use up your quota of three days, any homework submitted late will not be accepted and you will get 0 points for that homework.

When you submit a homework X days late, your quota gets decreased by X irrevocably. You can only be late by an integer number of days -- if you submit 10 hours after the deadline, for example, your quota is depleted by one day.

Exam Dates

The midterm will be held on Tuesday April 2 at the regular class meeting. The final will be held on Tuesday, May 14th at N104, LC, from 12.30--2.30 pm.

What we cover each week

See here for a summary of what we covered each week.

Handouts and Notes