The algorithm maintains both a sweep line and a beach line, which both move through the plane as the algorithm progresses. The sweep line is a straight line, which we may by convention assume to be vertical and moving left to right across the plane. At any time during the algorithm, the input points left of the sweep line will have been incorporated into the Voronoi diagram, while the points right of the sweep line will not have been considered yet. The beach line is not a straight line, but a complicated, piecewise curve to the left of the sweep line, composed of pieces of parabolas; it divides the portion of the plane within which the Voronoi diagram can be known, regardless of what other points might be right of the sweep line, from the rest of the plane. For each point left of the sweep line, one can define a parabola of points equidistant from that point and from the sweep line; the beach line is the boundary of the union of these parabolas. As the sweep line progresses, the vertices of the beach line, at which two parabolas cross, trace out the edges of the Voronoi diagram. The beach line progresses by keeping each parabola base exactly half way between the points initially swept over with the sweep line, and the new position of the sweep line. Mathematically, this means each parabola is formed by using the sweep line as the directrix and the input point as the focus. The algorithm maintains as data structures a binary search tree describing the combinatorial structure of the beach line, and a priority queue listing potential future events that could change the beach line structure. These events include the addition of another parabola to the beach line and the removal of a curve from the beach line. Each such event may be prioritized by the x-coordinate of the sweep line at the point the event occurs. The algorithm itself then consists of repeatedly removing the next event from the priority queue, finding the changes the event causes in the beach line, and updating the data structures. As there are O events to process and O time to process an event the total time is O.
Pseudocode
description of the algorithm. let be the transformation, where is the Euclidean distance between and the nearest site let be the "beach line" let be the region covered by site. let be the boundary ray between sites and. let be the sites with minimal -coordinate, ordered by -coordinate create initial vertical boundary rays while not IsEmpty do ← DeleteMin case of is a site in : find the occurrence of a region in containing, bracketed by on the left and on the right create new boundary rays and with bases replace with in delete from any intersection between and insert into any intersection between and insert into any intersection between and is a Voronoi vertex in : let be the intersection of on the left and on the right let be the left neighbor of and let be the right neighbor of in create a new boundary ray if, or create if is right of the higher of and, otherwise create replace with newly created in delete from any intersection between and delete from any intersection between and insert into any intersection between and insert into any intersection between and record as the summit of and and the base of output the boundary segments and endcase endwhile output the remaining boundary rays in
Weighted sites and disks
As Fortune describes in ref., a modified version of the sweep line algorithm can be used to construct an additively weighted Voronoi diagram, in which the distance to each site is offset by the weight of the site; this may equivalently be viewed as a Voronoi diagram of a set of disks, centered at the sites with radius equal to the weight of the site. Weighted sites may be used to control the areas of the Voronoi cells when using Voronoi diagrams to construct treemaps. In an additively weighted Voronoi diagram, the bisector between sites is in general a hyperbola, in contrast to unweighted Voronoi diagrams and power diagrams of disks for which it is a straight line.
