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 sparsest cut.

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.