Sweep line algorithm: Difference between revisions

Revision as of 15:04, 30 April 2008

Revision as of 15:05, 30 April 2008

Line 5:

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 the entire description could not fit into memory.

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, 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 complexity of [[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> and it also makes it possible to report all K intersections among any N segments in the plane in time complexity of [[Big O notation|O]]((N + K) log N) and space timecomplexity of [[Big O notation|O]](N) <ref>[http://www.cs.tufts.edu/comp/163/notes05/seg_intersection_handout.pdf Line Segment Intersection Using a Sweep Line Algorithm], Diane Souvaine, (2008)</ref>

Since then, this approach was used to design efficient algorithms for a number of problems, such as construction of the [[Delaunay triangulation]] or [[Boolean operations on polygons]].