Spring 2013: Computational Geometry, 22C:196:001
Coordinates
The course meets 9.30--10.45 am Tuesday and Thursday at
218 MLH (MacLean).
Instructor
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.
- Line Segment Intersection
- Polygon Triangulation
- Orthogonal Range Searching
- Point Location
- Voronoi Diagrams
- Arrangements
- Delaunay Triangulations
- Convex Hulls
- Quadtrees
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:
- Epsilon Approximations, Nets, and Discrepancy
- Nearest Neighbor Search in High Dimensions
- Clustering: the k-means algorithm
- Coresets
- The perceptron algorithm??
References will be posted subsequently.
Prerequisites
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
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
- First Day Handout
- Homework 1, due by 11:59 pm on Feb 7th.
- Homework 2, due by 11:59 pm on Feb 21.
- Homework 3, due by 11:59 pm on Thursday,
March 7th.
- Homework 4, due by 11:59 pm on Thursday,
March 28th.
- Some review questions for Midterm (in addition to HW questions):
2.5, 3.2, 3.14, 5.10, and 5.11. These are from the version available electronically via the library.
- Homework 5, due by 11:59 pm on Tuesday,
April 23rd.
- The sixth and last homework, due by 11:59 pm on Tuesday,
May 7th.