Sweep line algorithm

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 a geometric description of an IC was processed in parallel strips because the entire description could not fit into memory.

[citation needed] 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 in 1976.

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).

[2] Since then, this approach has been used to design efficient algorithms for a number of problems in computational geometry, such as the construction of the Voronoi diagram (Fortune's algorithm) and the Delaunay triangulation or boolean operations on polygons.

[citation needed] The sweeping approach may be generalised to higher dimensions.