Understanding the Voronoi diagram
Part II: The role of Fortune’s Algorithm
In Part I of this series, we took a look at the mathematical concepts behind the Voronoi diagram. Here, in Part II we now look at how the diagram can be created using Fortune’s Algorithm.
Originally published by Steven Fortune in 1986 in his paper, “A sweepline algorithm for Voronoi diagrams”, a sweep line algorithm or plane sweep algorithm is an algorithmic paradigm that uses a conceptual sweep line or sweep surface to solve various problems in Euclidean space and is one of the key techniques in computational geometry.
A line sweeps the plane from one side to the other in order to identify specific events on the plane in accordance to the program requirements. In this article, we use a vertical sweep line that sweeps from the left corner of the plane to the right. However, it is also a common approach to use a horizontal line that sweeps from top to bottom or vice versa.
Fortune’s algorithm has a worst case time complexity of O(n log(n)).
It is important to note that the problem of Voronoi diagrams can also be solved using other methods such as:
Divide and Conquer: This approach has the same time complexity as the sweep line approach i.e. O(n log(n)), however it is often tougher to implement as we need to merge the smaller Voronoi diagrams created in order to get the required output.
Randomized Incremental Construction: While simplistic and straightforward to implement, it may have a worst case time complexity of O(n²).
And so we can say that Fortune’s sweep line algorithm is fairly optimal.
Let us now walk through the steps of this algorithm to theoretically understand its working and consequently gain insight about the kind of data structures required to implement it.
We start with a vertical sweep line on the left side of the plane and sweep until we reach a site. A site is as a sweep line event at whose location some work is done.
When we reach a site, a parabolic region is created behind the sweep line. As the sweep line moves forward, the parabolic arc is always equidistant from the site and the sweep line. (Such a parabola is defined by every site to the left of the sweep line i.e. sites that the sweep line has passed over. Here, the locus of points that are closer to one specific site than any other site to the left of the sweep line is bound by its respective parabola.)
As we keep doing this for sites encountered by the sweep line, the arcs widen up and merge, these merged parts form Voronoi edges. The sequence of parabolic arcs is called the beach line. Thus, the part where two parabolic arcs join on the beachline describe a line segment and it is worth mentioning that this line segment will be equidistant from its two respective sites as well as the sweep line.
When three of these arcs come together, a Voronoi vertex is created. Thus vertex formed is also known as a circle event.
The sweep line proceeds to process all other site events and circle events. And whenever Voronoi vertices are formed on both sides of a Voronoi edge, that edge is part of our final output for the Voronoi diagram. Thus, an edge is associated with the sites on either side of it as well as the Voronoi vertices on both ends.
Note: Insertion of new sites on the beach line is done optimally using a sorted associative container like std::map (in C++) of the beach line data structure which is a balanced binary tree similar to an AVL tree.
Once there are no more sites to process, the algorithm is complete and any incomplete Voronoi edge goes out to infinity.
And there you have it, we now understand the essence of Fortune’s sweep line algorithm. Here is an animation that helps us make these concepts concrete in our minds.
If you want to try a similar implementation yourself, check out this amazing interactive demo tool which lets you plot your own points and see the algorithm work its magic!
It is also interesting to know that Fortune’s algorithm for line segments works in pretty much the same way. Here each end point of the segment as well as the body of the segment is modeled as a site. In order to improve our understanding, we may model each side of the segment as a separate site. Now, it’s a little easier to see all points equidistant from one side and the other side is viewed as a different cell. And so we form our Voronoi diagram, where we compute the beach line events as a combination of these three types of sites. But this requires some complex expressions and will be a discussion for another day.
