Sweep line algorithm

In computational geometry, a sweep line algorithm or plane sweep algorithm is a type of algorithm that uses a conceptual "sweep line" or "sweep surface" to solve various problems in Euclidean space. It is one of the key techniques in computational geometry.

The idea behind algorithms of this type is to imagine that a line (often a vertical line) is swept or moved across the plane, stopping at some points. Geometric operations are restricted to geometric objects that either intersect or are in the immediate vicinity of the sweep line whenever it stops, and the complete solution is available once the line has passed over all objects.

This approach may be traced to scanline algorithms of rendering in computer graphics, followed by exploiting this approach in early algorithms of integrated circuit layout design, in which geometric description of an IC was processed in parallel strips, because the entire description could not fit into memory.

Application of this approach led to a breakthrough in the computational complexity of geometric algorithms when Shamos and Hoey presented algorithms for line segment intersection in the plane, and in particular, they described how a combination of the scanline approach with efficient data structures (self-balancing binary search trees) makes it possible to detect whether there are intersections among N segments in the plane in time complexity of O(N log N) [Michael Shamos, Dan Hoey, "Geometric Intersection Problems", Proc. 17th Annu. IEEE Symp. Found. Computer Sci., pp.208-215 (1976)] and it also makes it possible to report all K intersections among any N segments in the plane in time complexity of O((N + K) log N) and space complexity of O(N) [ [http://www.cs.tufts.edu/comp/163/notes05/seg_intersection_handout.pdf Line Segment Intersection Using a Sweep Line Algorithm] , Diane Souvaine, (2008)]

Since then, this approach was used to design efficient algorithms for a number of problems, such as construction of the Delaunay triangulation or Boolean operations on polygons.

The approach may be generalised to higher dimensions.

References

See also

* Bentley-Ottmann algorithm
* Shamos-Hoey algorithm