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.