Fortune's Algorithm for computing the Voronoi Diagram.

Fortune's algorithm for computing the Voronoi diagram of a set of points is the most efficient algorithm. It proceeds by sweeping a line across the plane in which reside the set of points. When the sweepline encounters a point, an "edge event" is triggered. The edge of a Voronoi cell is formed from the intersection of parabolas, each of which has its focus at a point in the pointset and its directrix as the sweepline. Since a parabola is the locus of points equidistant from a point and a line (the focus and the directrix), the intersection of two parabolas gives points equidistant from their two foci, and therefore an edge of the Voronoi diagram.
A circle event is triggered when the sweepline reaches the bottom of a circle, centered at one of the points. When this event occurs, two edges have intersected in a point. The algorithm can also be described by a sweep-plane which intersects cones, each of which has its vertex at a point of the pointset, and sides with slope of 45°. The first movie of the sweep-plane algorithm was made by Daniela Schroll, University of Vienna (2000), while the author was guest professor at Vienna University of Technology; the second is by Nicholas Bergson-Shilcock, F&M (2006). Download all zipped movie files described on this page by clicking the Download button at the right. |

A three-dimensional visualization (animation) of Fortune's Algorithm. Daniela Schroll,

*Technische Universität Wien, Institut für Computergrafik und Algorithmen*, 2000. Click on the thumbnail to the left to watch the movie (if your browser will support it)., or download the zipped files (all five visualizations described on this page).Voronoi6X. This shows Fortune's algorithm for the Voronoi diagram with six control points. The parabolic "wave front" and the "circle events" are shown. Click the image to view, or click download to obtain all visualizations described on this page.

Voronoi 6Q. This shows Fortune's algorithm for the Voronoi diagram with six control points. The movie stops and asks questions of the student/user, who may then restart the movie. Show.

Voronoi10X and Voronoi12X. Similar to Voronoi6X, but with ten and twelve control points, respectively. Show 10X. Show 12X.

Voronoi 6Q. This shows Fortune's algorithm for the Voronoi diagram with six control points. The movie stops and asks questions of the student/user, who may then restart the movie. Show.

Voronoi10X and Voronoi12X. Similar to Voronoi6X, but with ten and twelve control points, respectively. Show 10X. Show 12X.

VoronoiVR. This movie combines conventional video with QuickTime Virtual Reality (QTVR). The movie stops, and the user can drag the objects in the scene to better see (in this example) the cones and the cutting plane. This movie cannot be uploaded to or downloaded from this site. Nicholas Bergson-Shilcock, F&M, 2006. It plays only in QuickTime Player 7. Please contact the author.