Sweep line algorithm

Sweep line algorithm or plane sweep algorithm is an approach for construction algorithms in computational geometry for solving various problems in the plane. It is one of key techniques in computational geometry.

The idea of the algorithms of this type is to imagine that a line (e.g., a vertical line) sweeps the plane stopping at some points and to restrict geometric operations necessary for finding the solution to geometric object that intersect or are in the immediate vicinity of a line whenever it stops.

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 whole data could not into computer memory.

Application of this approach has led to a breakthrough in computational complexity in geometric algorithms when Shamos and Hoey presented algorithms for line segment intersection in the plane, 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 O(N log N)

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

The approach may be generalised to higher dimensions.