Sweep line algorithm: Difference between revisions

Revision as of 07:36, 1 January 2007

Latest revision as of 08:05, 1 May 2025

(48 intermediate revisions by 32 users not shown)

Line 1:

{{Short description|Class of algorithms which use a moving line to solve geometrical problems}}

'''Sweep line algorithm''' or '''plane sweep algorithm''' is an approach for construction algorithms in [[computational geometry]] for solving various problems in the plane. It is one of key techniques in computational geometry.

[[File:Sweep-line-algorithm.gif|frame|right|Animation of [[Fortune's algorithm]], a sweep line technique for constructing [[Voronoi diagram]]s.]]

In [[computational geometry]], a '''Sweepsweep line algorithm''' or '''plane sweep algorithm''' is an approach[[algorithmic forparadigm]] constructionthat algorithmsuses ina [[computationalconceptual geometry]]''sweep line'' or ''sweep surface'' forto solvingsolve various problems in the[[Euclidean planespace]]. It is one of keythe critical techniques in computational geometry.

The idea of the algorithms of this type is to imagine that a line (e.g., a vertical line) sweeps the plane stopping at some points and to restrict geometric operations necessary for finding the solution to geometric object that intersect or are in the immediate vicinity of a line whenever it stops.

The idea of thebehind algorithms of this type is to imagine that a line (e.g.,often a vertical line) sweepsis swept or moved across the plane, stopping at some points. and to restrict geometricGeometric operations necessaryare for finding the solutionrestricted to geometric objectobjects that either intersect or are in the immediate vicinity of athe sweep line whenever it stops., and the complete solution is available once the line has passed over all objects.

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 whole data could not into computer memory.

==Applications==

ApplicationAn application of thisthe approach hashad led to a breakthrough in the [[Analysis of algorithms|computational complexity]] inof 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>[[Michael Shamos]], Dan Hoey, "Geometric Intersection Problems", Proc}}. 17th Annu. IEEE Symp. Found. Computer Sci., pp.208-215 (1976)</ref>{{citation

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

| last2 = Hoey | first2 = Dan

| contribution = Geometric intersection problems

| doi = 10.1109/SFCS.1976.16

| 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'' + ''K'') log ''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

| url = https://www.cs.tufts.edu/comp/163/notes05/seg_intersection_handout.pdf

| year = 2008}}.</ref>

Since then, this approach washas been used to design efficient algoritmsalgorithms for a number of problems in computational geometry, such as the construction of the [[Voronoi diagram]] ([[Fortune's algorithm]]) and the [[Delaunay triangulation]] or [[Booleanboolean operations on polygons]].

==Generalizations and extensions==

The approach may be generalised to higher dimensions.

Topological sweeping is a form of plane sweep with a simple ordering of processing points, which avoids the necessity of completely sorting the points; it allows some sweep line algorithms to be performed more efficiently.

The [[rotating calipers]] technique for designing geometric algorithms may also be interpreted as a form of the plane sweep, in the [[projective dual]] of the input plane: a form of projective duality transforms the slope of a line in one plane into the ''x''-coordinate of a point in the dual plane, so the progression through lines in sorted order by their slope as performed by a rotating calipers algorithm is dual to the progression through points sorted by their ''x''-coordinates in a plane sweep algorithm.<ref>{{cite conference

| last1 = Cheung | first1 = Yam Ki

| last2 = Daescu | first2 = Ovidiu

| editor1-last = Goldberg | editor1-first = Andrew V.

| editor2-last = Zhou | editor2-first = Yunhong

| contribution = Line segment facility ___location in weighted subdivisions

| doi = 10.1007/978-3-642-02158-9_10

| pages = 100–113

| publisher = Springer (1)

| series = Lecture Notes in Computer Science

| title = Algorithmic Aspects in Information and Management, 5th International Conference, AAIM 2009, San Francisco, CA, USA, June 15-17, 2009. Proceedings

| volume = 5564

| year = 2009}}</ref>

The sweeping approach may be generalised to higher dimensions.<ref>{{cite arXiv |last=Sinclair |first=David |eprint=1602.04707 |title=A 3D Sweep Hull Algorithm for computing Convex Hulls and Delaunay Triangulation |class=cs.CG |date=2016-02-11}}</ref>

==References==

<references/>

==References==

{{reflist}}{{Algorithmic paradigms}}

[[Category:Geometric algorithms]]

[[Category:1976 in computing]]