Fortune Sweep Algorithm
Now we take a look at a better way to calculate the 2D Voronoi diagram.† This algorithm was first introduced by Steven Fortune in  and is often referred to as Fortuneís Algorithm as a result.† This algorithm has complexity O(n log n), which is optimal for this problem.† The following sections introduce the different constructions and terminology that are used by the solution, followed by the algorithm itself.
A common way to simplify a proximity related problem such as computing the Voronoi diagram is to use a sweep line construction.† A sweep line splits the problem domain into two regions, an explored region and an unexplored region.† It applies an ordering to the problem because we reason about the explored area based on what weíve seen so far and ignore the unexplored area.† We can get away with not caring about the unexplored area by observing that only points that have reached the sweep line or crossed it can possibly affect the current computation since all other points are too far away.† The entire problem area is eventually examined by ďsweeping" the line across the set of points from one extreme to another.
Let's look at an example of the sweep line applied to calculating the Voronoi diagram of a single site.† Imagine our sweep line, denoted s, starts at the top of the image and sweeps down as seen in Figure 2.† The point set contains only one site p1.† How can we reason about the area above the sweep line?† Before the first and only site is encountered, there is nothing to reason about.† Once the sweep line has passed below site p1, what area must be in the Voronoi cell of site p1?† Since there could be a new site lurking just beneath the surface of the sweep line we can only reason that any point closer to p1 than to the sweep line itself must be in the Voronoi cell of site p1 at this moment in time. †It could be that the Voronoi cell of site p1 is much larger than what weíre assigning to it at this moment, but the sweep will eventually account for this.
Reasoning in this way divides the area above the sweep line into two disjoint regions separated by a parabola.† Points on the parabola are equidistant to p1 and the sweep line.† This dividing line is termed the beach line (for reasons that will soon become apparent).† The algorithm for computing the Voronoi diagram of a set of points depends entirely on how this beach line changes as the sweep moves through the space.† The beach lineís topology changes when a new arc is added or deleted.† The following sections look at when these events can occur.
Figure 2:† Sweep line passing over a single site.† We only reason about the area above the sweep line at any point in time.† The parabola is degenerate when it first hits the sweep line, creating a vertical line of zero area.
So what happens when there is more than one site during the sweep?† In Figure 3 we can see this situation.†
Figure 3: Two sites present
When a site hits the sweep line it is called a site event.† In Figure 4 we can see the site event where p2 hits the sweep line.† Note that it forms a degenerate parabola that intersects p1ís parabola at a single point.† Letís call this point of intersection q.† We know that q is equidistant to both p1 and p2, since it is on p1ís beach line which is the set of points of equal distance to p1 and the sweep line.† Furthermore, we know that no other site can be closer to q otherwise the beach line would not exist at that point (from the way we defined the beach line).† Therefore we know that this point must lie on the Voronoi edge that separates the two cells defined by sites p1 and p2.
Figure 4:† p2ís site event.† Point q must be equal distance to both p2 and p1.
As the sweep line continues downwards p2 begins to define its own parabola that intersects p1ís parabola twice as seen in Figure 5.† These intersections are termed breakpoints.† If we drew a circle that was centred on each breakpoint we would see that p1, p2, and the closest point on the sweep line all lie on the circumference of the circle.† Since this circle must be empty (if it wasnít then the breakpoint would not exist at that point) we can see that the breakpoints are defining the edges of the Voronoi diagram as the sweep line moves downwards.
Figure 5:† The breakpoints are defined by the intersection of the different arcs on the beach line.† They also trace out the Voronoi diagram edges.
The beach line now consists of three arcs - p2ís parabola and p1ís parabola that is divided into two pieces by p2.† The beach line is always defined by the parabola that is closest to the sweep line.† The appearance of the beach line at this point is where it gets its name Ė it looks like the arcs created by the meeting of the beach and the ocean.† Figure 6 shows the progression of the sweep line for two sites.
Figure 6:† The sweep line progression for two sites
This process can be extended to more than just two sites, by picturing each new site event creating a new parabolic arc and defining a new Voronoi edge as in Figure 7.† There is one last issue that remains to be looked at, and that is at points where arcs on the beach line disappear.† This is covered in the next section.
Figure 7:† The sweep line progression for three sites
Important:† The most important thing to realize about site events is that a site event is the only way a new arc can appear on the beach line .† When we look at the algorithm that uses the sweep line to calculate the Voronoi diagram this fact is crucial.
You can imagine that as new arcs appear along the beach line created by site events, old arcs that are far away from the sweep line must at some point disappear.† When would this happen?
In Figure 8 you can see a situation where this would occur.† The beach line originally consists of three arcs, α1, α2 and α3 as generated by three sites p1, p2, and p3 respectively.† As the sweep line moves downwards α2 is engulfed by its two neighbours.† This event is termed a circle event and can be seen in Figure 9.† Let point q be the intersection of these three parabolas at that moment.† A circle event gets its name because at the moment it occurs you could draw a circle passing through p1, p2, and p3 and the closest point on the sweep line and the origin would be centred on point q.† This circle exists because we know that each site is the same distance away from q which is equal to the distance to the sweep line (by the way we constructed the beach line in the first place!).† We also know that there canít be another site inside of this circle since then q would be closer to that new site than it is to the sweep line, contradicting the fact that q is on the beach line.
Figure 8:† Three sites p1, p2, and p3 creating three arcs α1, α2 and α3 respectively
Figure 9:† Circle event where α2 is engulfed by its two neighbours
Youíve probably already guessed that this will be a vertex in the Voronoi diagram under construction.† You could imagine the two converging breakpoints that are defining Voronoi edges meeting at point q, and only one breakpoint leaving Ė defining a Voronoi vertex of degree 3.† See Figure 10 for an animation showing this situation.† For Voronoi vertices of degree greater than 3 the same progression would happen, except there would be 2 or more arcs disappearing at the exact same point.
Figure 10:† Creation of a Voronoi vertex of degree 3
Important:† It turns out that the only way for an arc to disappear from the beach line is through a circle event .
We are now ready to look at the sweep algorithm for computing the 2D Voronoi diagram of a set of points.† The algorithm for this problem does not actually calculate the parabolas that define the beach line as we sweep through the problem space.† Doing so would be computationally expensive and as it turns out, unnecessary.† Instead, only instances when the beach line changes topology do we need to do calculations.† Weíve already seen the two times the beach line can change topology:† site events where a new site crosses the sweep line and circle events where an arc on the beach line disappears.
The sweep line algorithm requires three data structures to keep track of things:
∑ A priority queue to keep track of the site events and circle events
∑ A priority queue is used to tell us when the topology of the beach line could change.† The priority of an event is determined by when the sweep line will encounter it.† For example, if the sweep line starts at the top of the problem space and moves downwards, the site events would be given higher priority if they have a larger y-coordinate (assuming y increases in the upward direction).† Circle events are also given a priority by when the sweep line will encounter them.† In our example this would be the y-coordinate of the sweep line as it just grazes the bottom of the circle corresponding to the circle event.
∑ Site events will store their site.† Circle events will store the position they will occur, as well as a pointer to the arc (leaf) in the binary tree that will disappear when this circle event occurs.†
∑ The algorithm progresses by simply popping the highest priority event from the queue and calculating the manner in which the topology of the beach line changes.
∑ The site events are known beforehand and can be entered into the priority queue during initialization.† However, the circle events are detected as the beach line changes its shape, and need to be entered into the queue at that time.† More on this process can be found below.
∑ An edge vertex list to keep track of the Voronoi diagram under construction
∑ When a site event defines a new parabolic arc on the beach line it begins to trace out a new Voronoi edge.† Also, when a circle event occurs and two or more edges meet they define a Voronoi vertex at that point, and a new Voronoi edge will leave that vertex defined by the new breakpoint.† To maintain these edges and vertices as they are being created an edge vertex list is used.
∑ At the end of the algorithm this list will contain the Voronoi diagram we are trying to calculate.
∑ A balanced binary search tree to maintain the topology of the beach line
∑ A balanced binary search tree is used to maintain the status of the beach line.† See Figure 11 for an example of what the tree would look like in a sample problem.† Each leaf of the tree stores a site that defines an arc on the beach line.† Each internal node stores the two sites that define the breakpoints on the beach line.† Using this representation it becomes easy to determine where a new site event will affect the beach line.† In our example, we would simply compare the x-coordinate of the new site to each internal node to find the correct location along the beach line for this new arc.† This can be done in O(logn) time since we are using a balanced binary search tree.
∑ When a new arc appears on the beach line it will divide an existing arc into two segments.† To make the necessary changes to our tree we delete the leaf corresponding to the original arc that will be divided into two, and replace it with a subtree with three leaves.† The middle leaf will store the new site being added, and the other two leaves will contain the original site.† The internal nodes need to be updated to reflect the change in breakpoints.† The tree can be rebalanced if necessary.
∑ Finally, each leaf also stores a pointer to a circle event in the priority queue where the arc defined by this site will disappear.† If this event does not exist or hasnít been determined yet this pointer is set to null.† A circle event is calculated by comparing the breakpoints on either side of the arc.† If there are one or no breakpoints, no circle event will occur.† If there are two breakpoints, then a test needs to be made to see if these breakpoints will converge.† If they will converge, this means that this is a potential circle event and needs to be entered into the priority queue.
Figure 11:† Binary search tree and its correspondence to the beach line.† Internal nodes store the breakpoint information which is the two sites that are creating the breakpoint.† External nodes store the sites on the beach line, plus pointers to the circle events in which they will disappear.†
We are now ready to look at the algorithm for this process.
Main(list of sites)
Subtle Algorithm Issues
This algorithm has an O(n log n) running time and uses O(n) amount of storage.† These values are derived below.
Since we are using a balanced binary search tree any primitive operations such as finding the location of a site along the beach line or adding and deleting nodes will take O(log n) time.† Making changes to the priority queue will also take O(log n) time.† Any additions to the edge vertex list take a constant amount of time.† These three operations can happen for each event a constant number of times, which means that we spend O(log n) time per event.
So how many events do we have?† Obviously we have at least n events since we will have a site event for each point in our data set.† How many circle events will we have?† Each circle event corresponds to a vertex in the Voronoi diagram.† The false circle events are deleted from the priority queue before they are processed, and this deletion is performed while processing other real events in constant time.† Therefore false alarms do not contribute to the number of circle events processed.† So we can determine the number of circle events by knowing the upper bound on the number of vertices contained in our Voronoi diagram.† Using Eulerís formula for a connected planar embedded graph we can calculate this upper bound as 2n-5.† So this gives us a total of at most 3n-5 †events, each spending O(log n) time doing operations.† This gives us an overall running time of O(n log n).† The storage for the binary tree, priority queue, and edge vertex list is also a linear function of the number of points being examined.† Hence we have O(n) storage.