Plane Sweep Technique
The 'plane sweep' is one of the fundamental techniques used to solve two-dimensional geometric problems. This technique make possible to solve two-dimensional problems by a sequence of almost one-dimensional processing. Bentley and Ottmann [1] computes the intersections of n line segments in the plane by shifting a vertical line, H, known as sweepline, across the plane. As the sweep-line moves, it hits objects one by one. When an event happens (sweepline hits endpoint of the line segment or an intersection point); sweepline solves the portion of the problem that are on the sweepline.
Nonetheless, Sweep method of constructing a Voronoi diagram does not explicitly use the sweepline technique, since to construct Voronoi edges and Voronoi vertices on the sweepline one has to predict the positions of sites at the right side of the sweepline. Fortune [2] discovered a way around this problem. He recommended a planar transformation under which every site turn into the leftmost point of its Voronoi region, in order to be the first point hit at some stage in a left-to-right sweep. Subsequently, Seidel [3] and Cole [4] have shown the route to avoid this transformation. Because the bisector of a line and a non-incident point is a parabola, the boundary of the Voronoi region of sweep-line, H, is a connected chain of parabola segments whose topmost and bottommost edges tend to infinity. This chain is called the wavefront, W.
All through the sweep from one end to other, there are two categories of events make change in the structure of the wavefront, specifically when a new wave appears in wavefront and when an old wave disappears in wavefront. A new wave emerges in wavefront whenever the sweep line hits a new site. Consider two sites whose waves are adjacent in wavefront. The bisector of these two sites causes to a Voronoi edge to the left of wave front. Its continuation into the region of sweepline, is called a spike.
Spikes are tracks along which the waves are moving. A wave fades away from wavefront when it arrives at the intersection of two adjacent spikes. While keeping track of the wavefront one can preserve the Voronoi diagram of sweepline and of the sites to the left of sweepline. Once all sites have been detected and all intersections of spikes have been processed, Voronoi diagram of the set S is obtained by eliminating the wavefront and extending spikes to infinity. Although one wave may put in several segments in the wavefront, the size of the wavefront is O(n). The reason is that since any two parabolic bisectors can cross at most twice, the size of the wavefront is bounded by l_2(n)=2n-1, where ls(n) denotes the maximum length of a Davenport-Schinzel sequence over n symbols in which no two symbols appear s times each in alternating positions [5]. The balanced binary tree implements the wavefront and stores the segments in bottom-up fashion. This make possible to insert a wave, or remove a wave segment, in O(logn) time.
Prior to the sweepline starts, sort the sites by increasing x-coordinates and insert these sites into an event queue. Subsequent to each update of the wavefront, test newly adjacent spikes for intersection. If they intersect at some point, insert into the event queue the time, i.e. the position of the sweep line, when the wave segment between the two spikes arrives. Since the point at which wave arrives is a Voronoi vertex of V(S), there are only O(n) many events cause by spike intersections. In addition, each of the n sites makes an event happen. For every active spike, save its first intersection event. Consequently, the size of the event queue never exceeds O(n). This leads to the following result. Sweep technique offers the method of computing the Voronoi diagram of n points in the plane within O(n log n) time and linear space.
[1] J. L. Bentley and T. A. Ottmann,
Algorithms for reporting and counting geometric intersections, IEEE Trans.
Comput. C-28 (1979), 643-647.
[2] S. J. Fortune, A sweepline algorithm for Voronoi
diagrams, Algorithmica 2 (1987), 153-174.
[3] R. Seidel, Constrained Delaunay triangulations and
Voronoi diagrams, Report 260 IIG-TU, Graz, Austria (1988), 178-191.
[4] R. Cole, Reported by C. O'Dunlaing (1989).
[5] M. J. Atallah, Some dynamic computational geometry
problems, Comput. Math. Appl. 11 (1985), 1171-1181.
Control the program with mouse. Right Click the mouse to add a point on the right side of the sweep-line. Below follows an explanation of the various buttons and checkboxes.
This applet is created by Allan Odgaard & Benny Kjær Nielsen at the department of computer science, University of Copenhagen (DIKU).
