Sweep line algorithm: Difference between revisions

Revision as of 06:41, 27 February 2023

Revision as of 06:47, 27 February 2023

Line 10:

==Applications==

Application of this approach 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, 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 ''{{mvar|N''}} segments in the plane in [[time complexity]] of {{math|[[Big O notation|O]](''N''&nbsp; log&nbsp; '' N'')}}.<ref>{{citation

| last1 = Shamos | first1 = Michael I. | author1-link = Michael Ian Shamos

| last2 = Hoey | first2 = Dan

Line 17:

| pages = 208–215

| title = Proc. 17th IEEE Symp. Foundations of Computer Science (FOCS '76)

| year = 1976| s2cid = 124804 | url = http://euro.ecom.cmu.edu/shamos.html }}.</ref> The closely related [[Bentley–Ottmann algorithm]] uses a sweep line technique to report all ''{{mvar|K''}} intersections among any ''{{mvar|N''}} segments in the plane in time complexity of {{math|O((''N''&nbsp; +&nbsp; ''K'')&nbsp; log&nbsp; ''N'')}} and space complexity of {{math|O(''N'')}}.<ref>{{citation

| last = Souvaine | first = Diane | author-link = Diane Souvaine

| title = Line Segment Intersection Using a Sweep Line Algorithm