Content deleted Content added
m link souvaine |
templatize refs and clean up math |
||
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
| last1 = Shamos | first1 = Michael I. | author1-link = Michael Ian Shamos
| last2 = Hoey | first2 = Dan
| contribution = Geometric intersection problems
| doi = 10.1109/SFCS.1976.16
| page = 208–215
| title = Proc. 17th IEEE Symp. Foundations of Computer Science (FOCS '76)
| year = 1976}}.</ref> and it also makes it possible to report all ''K'' intersections among any ''N'' segments in the plane in time complexity of O((''N'' + ''K'') log ''N'') and space complexity of O(N).<ref>{{citation
| last = Souvaine | first = Diane | author-link = Diane Souvaine
| title = Line Segment Intersection Using a Sweep Line Algorithm
| url = http://www.cs.tufts.edu/comp/163/notes05/seg_intersection_handout.pdf
| year = 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]].
Line 12 ⟶ 23:
==References==
{{reflist}}
== See also ==
| |||