HMC Math 189A: Computational Geometry (Spring, 2002)
Course Project

Description

If you choose to do the course programming project, you will be excused from two homework assignments and the final exam. You must implement Fortune's algorithm for computing the Voronoi diagram for a set of points in the plane. Your program must be written in C, C++ or MATLAB. It should assume the input is given as a list of integer (x,y)-pairs listed one per line, as below:

123  19
-13  0
1028 13897
Your final output should be a drawing of your Voronoi diagram and the original data points, but this needn't be accomplished by your main program. For example, your main program may output 4-column data representing line segments, which may then be read and rendered by another package such as MATLAB. If you like, you are welcome to deal with this on your own. However, to make your life easier, I am providing simple MATLAB code in the form of vormat.m which should get the job done if you study it a little. You are welcome (and even encouraged) to modify this code however you like to suit your purposes.

You must submit all the source code for your project, together with its output (in graphical form only!) on several sample input files provided below. In addition, you must, for full credit, make up at least one "interesting" data set of your own and submit its results. You must also include a brief write-up describing your code. Mention any important implementation decisions you made, speed/memory optimizations you used (if any), and analyze the run time of your implementation to the best of your ability (I realize this may be especially tricky if you choose to use MATLAB, but give it a shot). Discuss any aspects of your implementation that you found interesting or noteworthy. One or two single-spaced pages should be plenty.

The main advice I can give you is to begin working on this yesterday. This is not an easy project (at least by my reconning... but maybe you CS geeks will crank it out in a few hours; I never know about you guys), so don't wait till the last minute! If you have any questions, feel free to ask me. I may even have an answer!

Data Sets

Small test sets - do not submit!
set0a - 6 random points, basic test
set0b - 4 points, tests degenerate case
set0c - 5 points, test degenerate more cases

Main data sets - courtesy of M. Goodrich
set1
set2
set3
set4
set5
set6
set7
set8
set9
set10

Three of my own - if your pogram doesn't read these, don't sweat it
(I'll try to get them cleaned up soon, but no promises)
new1
new2
new3

This project is based on one assigned by M. Goodrich at Johns Hopkins University for 600.488 Computational Geometry.
Return to: Math 189A Main Page * Greg Levin's Page * Department of Mathematics
Email: levin@hmc.edu