Now we take a look at a better way to calculate the 2D Voronoi diagram. This algorithm was first introduced by Steven Fortune in [2] 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.
Sections:
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.
Read full article from Sweep Algorithm
No comments:
Post a Comment