Spring 2007: Computational Geometry, 22C:196:005
In this course, we will discuss some of the algorithmic research
work done over the past decade or so on the following themes:
- Polynomial time approximation schemes for the Euclidean travelling
salesman problem and other related problems.
- Metric clustering (for example, partition a finite metric into
two sets so as to minimize sum of intra-cluster distances) and
geometric clustering (for example, k-means clustering).
- Subspace approximation, for example, finding the best subspace
of a specified dimension that best fits (according to some standard
measure of fit) a given set of points.
- Data structures for approximate nearest neighbour computation in
metric and geometric spaces.
- Geometric versions of the set cover problem, for example, find
the smallest number of point guards for a polygonal art gallery.
If time permits, we will also talk about (a) results on embedding metrics
into geometric spaces and their applications and (b) recent use of geometric
ideas in approximately solving combinatorial optimization problems like
The expectation from the students is that will they will (i) share in scribing
notes of the lectures, (ii) solve two or three homeworks, and (iii) either
(a) give a presentation at a time scheduled outside class hours, based on
their understanding of some agreed upon research paper, or (b) implement and
experimentally evaluate one or more of the algorithms for the problems
we will discuss in class, and submit a report based on this work. All
students in the course are not required, but are welcome, to attend
student presentations that will be made outside class hours. The standards
for (iii)(a) and (iii)(b) will be clarified at the beginning of the course.
Here is the schedule of talks.
If your talk is in B13, and you plan to use a projector,
make sure that you can get one from the office and set it
up with your laptop.
Monday, April 16, 12.30 to 1.30, B13: Gaurav
Wednesday, April 18, 12.30 to 1.30, B13: Meenal
Monday, April 23, 2.30 to 3.30, B13: Shobha
Wednesday, April 25, 12.30 to 1.30, B13: Jon
Friday, April 27, 1.30 to 2.30, B11: Chris
Wednesday, May 2, 12.30 to 1.30, B13: Erik
Friday, May 4, 9.00--10.00, B13: Matt