'''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 the key techniques in computational geometry.
The idea of thebehind algorithms of this type is to imagine that a line (e.g.,often a vertical line) sweepsis swept or moved across the plane, stopping at some points. and to restrict geometricGeometric operations necessary forare finding the solutionrestricted to geometric objectobjects that either intersect or are in the immediate vicinity of athe 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 algorithm]]s 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 wholethe dataentire description could not intofit computerinto memory.
Application of this approach has led to a breakthrough in the [[computational complexity]] inof 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 tree]]s) makes it possible to detect whether there are intersections among N segments in the plane in time [[Big O notation|O]](N log N) <ref>[[Michael Shamos]], Dan Hoey, "Geometric Intersection Problems", Proc. 17th Annu. IEEE Symp. Found. Computer Sci., pp.208-215 (1976)</ref>
Since then, this approach was used to design efficient algoritms 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.
