Voronoi Diagram: Fortune's Algorithm
a sweepline algorithm
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.
A circle event is triggered when the sweepline reaches the bottom of a circle, centered at one of the points, with radius ... When this event occurs, two edges have intersected in a point.
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.
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).
Movies show Fortune's algorithm with six, ten, and twelve points. One six-point movie pauses to pose questions to the viewer. The sweep-plane movie has eight points. Remember the guidelines for use of these movies.
|
|
|
|
|
|
A New Initiative: A Movie with an Embedded Virtual-Reality Scene
There is also a three-dimensional visualization of Fortune's algorithm. In an effort to display a complex three-dimensional scene so that all of its parts — cones, sweep plane, etc. — are seen in their relationship, we have begun to construct QuickTime movies which pause at particular times in the algorithm and present the user with a virtual-reality display which the user can grab, and turn in different ways so as to examine the interrelated parts. After viewing the scene at a moment in time, the user can resume to watching the scene evolve in time. One such movie was made by Nicholas Bergson-Shilcock (F&M, 2006).
