Revision as of 20:28, 29 March 2014 edit David Eppstein (talk \| contribs) Autopatrolled, Administrators 235,763 edits m Reverted edits by 130.88.194.33 (talk) to last version by Addbot ← Previous edit		Revision as of 16:59, 26 May 2015 edit undo BD2412 (talk \| contribs) Autopatrolled, Administrators 2,528,335 edits m minor fixes, mostly disambig links using AWB Next edit →
Line 1: [[~~Image~~File:Fortunes-algorithm.gif\|frame\|right\|Animation of [[Fortune's algorithm]], a sweep line technique for constructing [[Voronoi diagram]]s.]] In [[computational geometry]], a '''sweep line algorithm''' or '''plane sweep algorithm''' is a type of algorithm that uses a conceptual ''sweep line'' or ''sweep surface'' to solve various problems in [[Euclidean space]]. It is one of the key techniques in computational geometry. Line 9: ==Applications== Application of this approach led to a breakthrough in the [[Computational complexity theory\|computational complexity]] of geometric algorithms when [[Michael Ian Shamos\|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>{{citation \| last1 = Shamos \| first1 = Michael I. \| author1-link = Michael Ian Shamos \| last2 = Hoey \| first2 = Dan

Sweep line algorithm: Difference between revisions