Sweep line algorithm: Difference between revisions

Revision as of 18:26, 1 January 2007

Revision as of 03:45, 6 January 2007

Line 7:

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 [[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 algoritmsalgorithms 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.