Computing the Voronoi Diagram

We now want to compute the Voronoi Diagram. Since we know that each Voronoi region $reg(p_i)$ is delimited by the bisectrix of $p_i$ with some other points, it can be computed by computing the intersection of $n-1$ half-planes. Since this operation can be done in $O(n\log n)$ (see Section 4.2 of (5)), this leads to an $O(n^2\log n)$ algorithm to compute the whole Voronoi diagram. Can we do better? Since we know that Voronoi Diagrams are dual to Delaunay Triangulations, one thing we can do is to compute the Delaunay Triangulation, which can be done in $O(n\log n)$ time, and then computing the dual. This gives us a totally correct algorithm to compute Voronoi Diagram which runs in $O(n\log n)$ time. However, there are situations, like the one we will discuss in Section 3.4, where it is not even clear that the Delaunay Triangulation is something well-defined. Even if it was, then it would not directly implies that it is still dual to Voronoi Diagram. We then need an algorithm which allows to compute the Voronoi Diagram directly.

One may have the intuition of designing some plane-sweep algorithm. However, the problem we have to face is to monotonize the process of drawing the Voronoi edges. If you sweep your plane, say from top to bottom, then it may happen that at some point, the edges you must draw are generated from sites that are situated below the sweep line and of which you are not yet aware. The idea Fortune introduced () is to not draw the edges directly where the sweep line is situated, but to do it somewhere behind the sweep line.

Here is the main idea of his algorithm: if you draw a horizontal line on the plane, and you use it to draw parabolas having that line as directrix and the points situated above the line as foci, then the intersection between each pair of parabolas are situated on the bisectrix of their foci. To see this, remember that a parabola is defined as the set of points which are equidistant from a line and a point. By transitivity, the intersections of two parabolas having the same directrix are therefore equidistant from their respective foci. The plane sweep algorithm proposed by Fortune then not only uses a sweep line, but also a beach line. The beach line is the border of the region formed by the union of all the open regions situated above the parabolas. It is (probably) called a beach line because each portion of parabola of witch it is formed looks like a wave. Before to go forward, lets take a look at how you can you that beach line to draw the Voronoi Diagram of a set of points.

Figure 5: Plane Sweep Voronoi Applet.

The applet shown on Figure 5 demonstrates how the algorithm works. You can click on it for a step by step demonstration. If you want a full run of the algorithm, you can go in the Voronoi menu and click Run!. If you want to see it again, you can go in the same menu, and chose Initialize. It may happen that you experiment some problems if two points have the same $y$-coordinate. If this happen to you, just re-initialize the applet.

The red line is your sweep line. As it goes down, you can see that the parabolas are getting wider. There are two things we must know in order to be able to maintain the beach line properly: when to insert new waves, and when to remove waves. Those actions correspond to the two kinds of events you put in your event queue: site events and circle events. Site events, as you may expect, correspond to the points of which you are computing the Voronoi Diagram. When you have a new site above your sweep line, you have a new parabola on your beach line. When the site is on the sweep line, then the parabola degenerates to a half-line perpendicular to the directrix (the sweep line). That half line intersects an already existing wave and splits it in two. Notice that this implies that a single parabola can contribute for more than one wave. Circle events tell you when you should remove a wave from the beach line. Notice that a wave disappears when the two edges on its extremities converge to a Voronoi edge. At this point, you are then situated at equal distance from three sites: two pairs of sites form the two bisectrix, but those two pairs share a common site which is the one whose region is just above the two intersecting bisectrix. Those three sites define a unique circle whose center is the Voronoi edge, and it is that circle that we use for circle events. Notice that the circle event should not be scheduled in the event queue at the center of the circle, since the beach line is above the sweep line. Instead, it has to be scheduled for the moment when the sweep line is at the same distance from the circle center than from its three defining sites. This will happen when the sweep line is at the very bottom of the circle. Finally, notice that since there may have many more circle events than there are waves to removes, some circle events have to be considered as false alarms. False alarms have to be identified each time you modify the beach line status, so modifications of the beach line status also modify the event queue. A detailed description of the algorithm and a proof of its correctness can be found in (5).

Now, if you use an appropriate data structure to store your beach line, each site event can be processed in $O(\log n)$ time. Basically, what you need to do is to find the wave which is intersected, and to add and remove some circle events from the event queue. Since the latter can be done in constant time, the most costly operation is the search for the appropriate wave, and this is where the $O(\log n)$ comes from. Since there are $n$ such site events, the processing time for those ones is  $O(n\log n)$. Now, we know from Section 1.3 that there is a linear number of Voronoi vertices, so there is a linear number of circle events that will actually be processed (that wont be false alarms). Therefore, the total running time of the plane sweep algorithm is  $O(n\log n)$.