Voronoi Diagrams and Delaunay Triangulations

David Mount of the University of Maryland has graciously let me include excerpts from his course notes here: (See his course page for all of his notes.)

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.html

Here'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