Triangulation: Fortune's Algorithm Details

Last time, we saw how Fortune used a sweepline to produce a Voronoi diagram for a set of points. This time, we investigate how it works. First, I repeat the earlier diagram, because it is quite pleasant to watch:

Let us know consider a snapshot of a single sweepline location:

There are two lines in this diagram - the sweepline, and the beachline - and they split the diagram into three parts. The first is the area below the sweepline. In this area are points which have not been encountered by the sweepline as it proceeds downwards, and we cannot reason about it. The second is the area above the beachline. In this area, the final shape of the Voronoi diagram is known.

How do I know that the Voronoi diagram is known? Consider that, because it is constructed from pieces of parabolas, any point on the beachline is the same distance away from the sweepline as it is from a visited site. Similarly, any point above the beachline must be closer to a visited site than it is to the sweepline. The only sites that have not been considered for inclusion in the final diagram are those which are below the sweepline; hence, any point above the beach line must be closer to a visited site than it can be to any unvisited site. Therefore, the Voronoi cell containing the point in question is already determined.

There is a third part to the diagram, though: the space below the beachline and above the sweepline. There are no unvisited sites in this location; they are all below the sweepline. We would also be able to determine the rest of the diagram from the information that we have (assuming there were no other unvisited sites) by extrapolating the beachline's intersection points, since they travel along straight lines. However, this part of the diagram changes depending on the presence of sites that we have not yet visited:

If Schrodinger's cat were to escape its box, it would probably prefer to spend its time in this middle area.

Let us now consider the beachline itself, and how it changes over time as the sweepline moves. It clearly changes shape as the sweepline descends, but a topologist might call this a 'continuous deformation' for most of the sweep, since the number of arcs in the sweepline, and the horizontal order of their intersection points, does not change.

There are only two ways that the topology of the beachline changes. The first is the more obvious of the two: when the sweepline encounters an unvisited point, a vertical line pierces the arc directly above it, and splits it into two, and a new arc is born between two pieces of the existing one. This is called a 'site' event. We know ahead of time when site events occur: when the sweepline's y coordinate matches that of a site.

The only other time when the beachline topology changes is when two of its intersection points meet, causing the arc between them to disappear from the beachline. For a given beachline, we can determine when this occurs as well. Say you have three consecutive beachline arcs, generated by sites A, B, and C. The intersection Iab of sites A and B is located at the circumcircle of site A, site B, and a point Sab located directly below Iab on the sweepline. Similarly, the intersection Ibc of sites B and C is located at the circumcircle of site B, site C, and a point Sbc located directly below Ibc on the sweepline. If the points Sab and Sbc are getting closer together as the sweepline descends, they will eventually meet at a new point, called Sac, and at that time, the arc from site B will be squeezed out of existence by arcs from sites A and C. These squeezing events are known as 'circle' events because of how their timing is determined, and they occur when the sweepline's y coordinate matches that of Sac. (A bit of linear algebra can calculate the location of Iac by finding the point of intersection of the bisector of sites A and B and the bisector of sites B and C, and the radius of that circle is just the distance between Iac and either point.)

In Fortune's algorithm, the sweepline is not continuously swept. The sweepline is only used as a conceptual tool to prove the correctness of the algorithm; instead the algorithm jumps from event to event based on the known Y-coordinate of their occurrence. Thus, the algorithm can be broken down simply into the following:

Get the next event that will change the beachline (whether it be a site event or a circle event), and process it, changing the beachline accordingly.

The Delaunay triangulation of the point set falls out of the changes to the beachline. Whenever a site event happens, and an existing beachline arc is split by a new arc, the sites corresponding to the splitter and splittee are joined by a Delaunay edge. Whenever a circle event happens, the sites for the arcs on either side of the middle, squeezed arc are joined by a Delaunay edge, and a Voronoi vertex is created at the circumcenter of the three arc sites.

There is some subtletly in actually implementing this routine, however:

• The list of circle events is not known ahead of time, and more importantly, it changes over time as new arcs are added to the beachline by site events and old arcs are squeezed away by other circle events.
• You need a flexible data structure to efficiently store and change the beachline as the sweepline moves. You can't use a linked list because searching is O(n), and you can't use an array because insertion and deletion is O(n).
• There is a bit of special case handling to take care of multiple sites with equal Y-coordinates at the top of the set. Each of these will be on the convex hull and thus need to be connected via Delaunay edges.
• There is a bit more special case handling for site events which intersect the beachline at an existing intersection point. This is essentially a combined site-circle event, and generates a Delaunay edge between the new site and the sites of the arcs on either side of the interseciton point.
• I believe, but have not proven, that in the event of a tie between the next site and circle event, you should process the circle event first. It may just come down to which triangulation of a circumscribed polygon the algorithm will produce.

Fortune's algorithm is not for the faint of heart, if you are considering implementing it. In broad terms, I would consider it to be a fair assigment for a third-year course in a university computer science degree program.