Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Sweep line algorithm
open-in-new
<h2 id="applications">Applications</h2> <p>An application of the approach had led to a breakthrough in the <a href="/facts/Analysis_of_algorithms/pStoBgBn">computational complexity</a> of geometric algorithms when <a href="/facts/Michael_Ian_Shamos/38cn2KNA">Shamos</a> and Hoey presented algorithms for <a href="/facts/Line_segment_intersection/RwH57yPq">line segment intersection</a> in the plane in 1976. In particular, they described how a combination of the scanline approach with efficient data structures (<a href="/facts/Self-balancing_binary_search_tree/W7WAsES0">self-balancing binary search trees</a>) makes it possible to detect whether there are intersections among N segments in the plane in <a href="/facts/Time_complexity/77T62gmf">time complexity</a> of <a href="/facts/Big_O_notation/weFFjSWg">O</a>(<i>N</i> log <i>N</i>).<a class="footnote-ref" id="fnref:1" href="#fn:1"><sup>1</sup></a> The closely related <a href="/facts/Bentley%25E2%2580%2593Ottmann_algorithm/djAFj5I5">Bentley–Ottmann algorithm</a> uses a sweep line technique to report all K intersections among any N segments in the plane in time complexity of O((<i>N</i> + <i>K</i>) log <i>N</i>) and space complexity of O(<i>N</i>).<a class="footnote-ref" id="fnref:2" href="#fn:2"><sup>2</sup></a> </p><p>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 <a href="/facts/Voronoi_diagram/AhQY5LD8">Voronoi diagram</a> (<a href="/facts/Fortune%2527s_algorithm/FDUyGGDJ">Fortune's algorithm</a>) and the <a href="/facts/Delaunay_triangulation/6VRk7cS9">Delaunay triangulation</a> or <a href="/facts/Boolean_operations_on_polygons/5lp152nx">boolean operations on polygons</a>. </p> <h2 id="generalizations-and-extensions">Generalizations and extensions</h2> <p>Topological 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. </p><p>The <a href="/facts/Rotating_calipers/SkbtSxWV">rotating calipers</a> technique for designing geometric algorithms may also be interpreted as a form of the plane sweep, in the <a href="/facts/Projective_dual/dxrjhRbB">projective dual</a> of the input plane: a form of projective duality transforms the slope of a line in one plane into the <i>x</i>-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 <i>x</i>-coordinates in a plane sweep algorithm.<a class="footnote-ref" id="fnref:3" href="#fn:3"><sup>3</sup></a> </p><p>The sweeping approach may be generalised to higher dimensions.<a class="footnote-ref" id="fnref:4" href="#fn:4"><sup>4</sup></a> </p> <h2 id="references">References</h2> <ol> <li id="fn:1"><p>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. <a href="/wiki/Michael_Ian_Shamos" target="_blank">/wiki/Michael_Ian_Shamos</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li> <li id="fn:2"><p>Souvaine, Diane (2008), Line Segment Intersection Using a Sweep Line Algorithm (PDF). <a href="/wiki/Diane_Souvaine" target="_blank">/wiki/Diane_Souvaine</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></p></li> <li id="fn:3"><p>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. <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></p></li> <li id="fn:4"><p>Sinclair, David (2016-02-11). "A 3D Sweep Hull Algorithm for computing Convex Hulls and Delaunay Triangulation". arXiv:1602.04707 [cs.CG]. <a href="/wiki/ArXiv_(identifier)" target="_blank">/wiki/ArXiv_(identifier)</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></p></li> </ol>