In computational geometry, a sweep line algorithm or plane sweep algorithm is an algorithmic paradigm that uses a conceptual sweep line or sweep surface to solve various problems in Euclidean space. It is one of the critical 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.
Applications
editAn application of the approach had 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).[1] The closely related Bentley–Ottmann algorithm uses a sweep line technique 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).[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.
Generalizations and extensions
editTopological sweeping is a form of plane sweep with a simple ordering of processing points, which avoids the necessity of completely sorting the points; it allows some sweep line algorithms to be performed more efficiently.
The rotating calipers technique for designing geometric algorithms may also be interpreted as a form of the plane sweep, in the projective dual of the input plane: a form of projective duality transforms the slope of a line in one plane into the x-coordinate of a point in the dual plane, so the progression through lines in sorted order by their slope as performed by a rotating calipers algorithm is dual to the progression through points sorted by their x-coordinates in a plane sweep algorithm.[3]
The sweeping approach may be generalised to higher dimensions.[4]
References
edit- ^ Shamos, Michael I.; Hoey, Dan (1976), "Geometric intersection problems", Proc. 17th IEEE Symp. Foundations of Computer Science (FOCS '76), pp. 208–215, doi:10.1109/SFCS.1976.16, S2CID 124804.
- ^ Souvaine, Diane (2008), Line Segment Intersection Using a Sweep Line Algorithm (PDF).
- ^ Cheung, Yam Ki; Daescu, Ovidiu (2009). "Line segment facility location in weighted subdivisions". In Goldberg, Andrew V.; Zhou, Yunhong (eds.). Algorithmic Aspects in Information and Management, 5th International Conference, AAIM 2009, San Francisco, CA, USA, June 15-17, 2009. Proceedings. Lecture Notes in Computer Science. Vol. 5564. Springer (1). pp. 100–113. doi:10.1007/978-3-642-02158-9_10. ISBN 978-3-642-02157-2.
- ^ Sinclair, David (2016-02-11). "A 3D Sweep Hull Algorithm for computing Convex Hulls and Delaunay Triangulation". arXiv:1602.04707 [cs.CG].
