CS507A: Computational Geometry - Projects

The Web project involves publishing a tutorial introduction to a simple idea and is divided into two parts: the HTML document (counts for 12%) and the interactive Java applet (counts for 20%). Both the HTML document and the Java applet are due December 3rd and the entire finished project must be installed in the Computational Geometry Laboratory by that date. For a better idea of what is expected,, take a look at Godfried Toussaint's previous years projects.

The topic for your project is fairly open, but you should discuss it with me. Your work should pertain to some basic concept or algorithm in geometry and involve reading at least one research paper.

Your Projects:

Detour: On a road, the detour between two points is the ratio between the distance to drive along the road, and the straight line distance. How can you find the two points that have the largest detour? (Chosen by Olivier Duguay)
Primal-dual transforms: We will see later in class several simple methods to transform a problem on lines into a problem on points and vice-versa. These methods offer some fascinating insights into many problems in geometry.(chosen by Chris Elliott)
Randomized incremental trapezoidation: how to decompose the plane into trapezoids. (Chosen by Jukka Olavi Kaartinen)
Computational Origami (chosen by Christian Lavoie).
From ranking to selection:If we have an algorithm that solves a ranking problem (how many statues are smaller than this one?), it is often possible to solve the associated selection problem (which is the k-th smallest statue?) with about the same speed. This project will explore techniques to do this. (Chosen by Thomas Lemaire)
Area and Volume:How to quickly compute areas and volumes. (chosen by Lianzhen Luo)
Ham-sandwich and other cuts (chosen by Danielle MacNevin).
Linear programming algorithms in geometry (chosen by Conor Meagher)
Hausdorff and Frechet distances:To evaluate how two roads differ, you can do several things. You could drive on one of the roads, and at every point find the distance to the closest point on the other road. The largest distance observed is the Hausdorff distance. You could also drive with two cars, one on each road, trying to synchronize the speeds cleverly, and record at every point the distance between the two cars. This is the Frechet distance. How to compute them, and how do they compare? (chosen by Stéphane Pelletier)
Enumerating triangulations (chosen by Ajit Rajwade)
Kirkpatrick's Point location data structure: data structure that decides where you are on a map. (Chosen by Paul Sandulescu)
Voronoi diagram algorithms and variants (chosen by Tomislav Vrljicak)

Unselected topics

From decision to optimization:If we have an algorithm that solves a decision problem (can we fit this statue into a box of size x?), it is often possible to solve the associated optimization problem (what is the smallest box that will fit the statue?) with about the same speed. This project will explore techniques to do this.
Red-blue line segment intersection:given blue and red segments in the plane, find all the intersections that involve a blue and a red segment.
Degree of operations:To decide if a point is to the right of another, you have to decide a linear inequality. To decide if a point is above a line, you have to decide a quadratic inequality. In general, what is the degree of the polynomials you have to decide to do some given task?
Robust regression methods:Given points on the plane, find a line that is "close" to the points. Some definitions of close are robust, that is, if you perturb a few data points, even by a lot, the line doesn't move too far.