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:


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

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.

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