Can someone give an easy explanation for sweep line algorithm ? I am not able to understand it?

Question

I am studying Geometry for Computing and I am stuck with how my book mentions Sweep line algorithm and gives no clear explanation about it ? A better resource will also be appreciated I just want to learn this new concept.

Answer 1

Sweep line is not an algorithm, it is a concept used in many algorithms. "A sweep line algorithm" is not any specific algorithm, it can refer to any algorithms that are described or defined using a sweep line concept.

Instead of a line, you could just as well think of it as the surf line on incoming tide, or the current moment marker along a video editing timeline. The position of the line represents the progress of the algorithm, and the actions done are described with respect to the sweep line.

The Wikipedia article on Fortune's algorithm for constructing a Voronoi diagram from a set of points describes one sweep line algorithm pretty well. The sweep line describes which points have been examined and considered, and the beach line (or more properly, the beach, or the region between the sweep line and the beach line) describes the region whose Voronoi diagram isn't fixed/determined yet.

It is important that you do not think that sweep line algorithms can be implemented using a for loop, to "sweep" a variable through the plane. No, the sweep line is just a concept whose purpose is to let you focus on what happens at each stage as the algorithm progresses, in a visual way.

In practice, as you examine the algorithm, you can find the rules for the locations of the sweep line with respect to the points to be added for the diagram; it is over these locations, in increasing order, that Fortune's algorithm "loops" over. In a very real sense, the priority queue contains those locations, inserted as they become known; and the binary search tree describes the structure of the beach region (the parabolas that eventually describe the vertices in the Voronoi diagram).