Dave Mount's lecture notes on Voronoi Diagrams.

There are currently no notes for the seep line algorithm I described in class. It's my own interpretation of Fortune's sweep line algorithm. The following link describes Fortune's algorithm. It has a couple of good pictures:

http://www.cg.tuwien.ac.at/studentwork/CESCG99/RCuk/

Here's a demo of Voronoi diagrams and Delaunay triangulations:

http://ra.cfm.ohio-state.edu/~zhao/algorithms/delaunay/delaunay.htmlHere's another demo. This one (if you figure out the interface) is cool because it lets you watch what happens as the points move around.

http://www.angelfire.com/mt/ofolives/DotPlacer.html

Daniel Sleator Last modified: Fri Feb 16 11:30:59 EST 2001