This page briefly describes what a Voronoi diagram is and provides an interactive demonstration of how these can be created using Fortune's plain-sweep algorithm.
The goal of the page is to give you an intuitive understanding of how Fortune's algorithm works and how Voronoi diagrams look, so if you have never heard of these diagrams we suggest that you follow some of the links given to get a better understanding of the theoretical aspects of Voronoi diagrams.
Imagine you have a map over a city with n cell phone masts. A cell phone always connects to the closest mast, so you'd like to split up the city in zones, where each zone has exactly one cell phone mast and each location inside such a zone is closest to the cell phone mast found in the same zone.
The result of such a partitioning is often referred to as a Voronoi diagram and can be created in O(n log n) time by various algorithms. This is also a lower limit.
In the above example we have transformed the problem of finding the closest mast to the problem of finding the zone in which we are located (also known as the point location problem). This can be determined in logarithmic time instead of the linear time, which would be required for finding the nearest mast if no preprocessing was done. Naturally you'll need to query the Voronoi diagram more than once to make up for this preprocessing time.
Though given a Voronoi diagram we can solve a lot of other geometrical problems such as convex hull and Delaunay triangulation.
The source is available as a gzip'ed tar archive (5.5 Kb).
You control the program with your mouse. At any time you can click on the right side of the sweep-line to add a point. Below follows an explanation of the various buttons and checkboxes.
If you draw a perfect circle of points all the zones should meet in the center of this circle. Now try to spoil this feature by adding a point in the middle of the circle. Even if you didn't succeed in making the circle perfect then try it anyway.