Revision as of 05:50, 1 May 2025 edit 2403:580b:9d25:0:218d:6f8d:7c39:6cda (talk) →Applications ← Previous edit		Latest revision as of 08:05, 1 May 2025 edit undo Altenmann (talk \| contribs) Autopatrolled, Extended confirmed users, Pending changes reviewers 244,949 edits No edit summary
Line 7: ==Applications== ~~Application~~An application of the approach had led to a breakthrough in the [[Analysis of algorithms\|computational complexity]] of geometric algorithms when [[Michael Ian Shamos\|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 tree]]s) makes it possible to detect whether there are intersections among {{mvar\|N}} segments in the plane in [[time complexity]] of {{math\|[[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