Sweep line algorithm - Revision history

Altenmann at 08:05, 1 May 2025

2025-05-01T08:05:36Z

← Previous revision		Revision as of 08:05, 1 May 2025
Line 7:		Line 7:

	==Applications==		==Applications==
	~~Application~~ of the 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 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		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		\| last1 = Shamos \| first1 = Michael I. \| author1-link = Michael Ian Shamos
	\| last2 = Hoey \| first2 = Dan		\| last2 = Hoey \| first2 = Dan

2403:580B:9D25:0:218D:6F8D:7C39:6CDA: /* Applications */

2025-05-01T05:50:16Z

Applications

← Previous revision		Revision as of 05:50, 1 May 2025
Line 7:		Line 7:

	==Applications==		==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 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		Application of the 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 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		\| last1 = Shamos \| first1 = Michael I. \| author1-link = Michael Ian Shamos
	\| last2 = Hoey \| first2 = Dan		\| last2 = Hoey \| first2 = Dan

David Eppstein: /* Generalizations and extensions */ supply requested citation

2025-04-09T06:14:04Z

Generalizations and extensions: supply requested citation

@@ Line 25: / Line 25: @@
 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.{{cn|date=November 2023}}
+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
 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>

David Eppstein: /* History */ plausible but entirely unsourced; remove

2025-04-09T06:05:31Z

History: plausible but entirely unsourced; remove

← Previous revision		Revision as of 06:05, 9 April 2025
Line 5:		Line 5:

	The idea behind algorithms of this type is to imagine that a line (often a vertical line) is swept or moved across the plane, stopping at some points. Geometric operations are restricted to geometric objects that either intersect or are in the immediate vicinity of the sweep line whenever it stops, and the complete solution is available once the line has passed over all objects.		The idea behind algorithms of this type is to imagine that a line (often a vertical line) is swept or moved across the plane, stopping at some points. Geometric operations are restricted to geometric objects that either intersect or are in the immediate vicinity of the sweep line whenever it stops, and the complete solution is available once the line has passed over all objects.

	==History==
	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 a geometric description of an IC was processed in parallel strips because the entire description could not fit into memory.{{Citation needed\|date=May 2009}}

	==Applications==		==Applications==

AnomieBOT: Dating maintenance tags: {{Cn}}

2023-11-20T05:06:00Z

Dating maintenance tags: {{Cn}}

← Previous revision		Revision as of 05:06, 20 November 2023
Line 28:		Line 28:
	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.		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.{{cn}}		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.{{cn\|date=November 2023}}

	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>		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>

Altenmann: added Category:1976 in computing using HotCat

2023-11-20T04:45:06Z

added Category:1976 in computing using HotCat

← Previous revision		Revision as of 04:45, 20 November 2023
Line 35:		Line 35:
	{{reflist}}{{Algorithmic paradigms}}		{{reflist}}{{Algorithmic paradigms}}
	[[Category:Geometric algorithms]]		[[Category:Geometric algorithms]]
			[[Category:1976 in computing]]

Altenmann: /* Generalizations and extensions */

2023-11-20T04:43:29Z

Generalizations and extensions

← Previous revision		Revision as of 04:43, 20 November 2023
Line 28:		Line 28:
	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.		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.		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.{{cn}}

	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>		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>

Altenmann: /* Applications */

2023-11-20T04:42:49Z

Applications

← Previous revision		Revision as of 04:42, 20 November 2023
Line 10:		Line 10:

	==Applications==		==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'' log ''N'')}}.<ref>{{citation		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 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		\| last1 = Shamos \| first1 = Michael I. \| author1-link = Michael Ian Shamos
	\| last2 = Hoey \| first2 = Dan		\| last2 = Hoey \| first2 = Dan
Line 23:		Line 23:
	\| year = 2008}}.</ref>		\| year = 2008}}.</ref>

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

	==Generalizations and extensions==		==Generalizations and extensions==

Kmschaal: Replaced animation with a more sophisticated version for better illustration

2023-04-24T15:54:18Z

Replaced animation with a more sophisticated version for better illustration

← Previous revision		Revision as of 15:54, 24 April 2023
Line 1:		Line 1:
	{{Short description\|Class of algorithms which use a moving line to solve geometrical problems}}		{{Short description\|Class of algorithms which use a moving line to solve geometrical problems}}
	[[File:~~Fortunes~~-algorithm.gif\|frame\|right\|Animation of [[Fortune's algorithm]], a sweep line technique for constructing [[Voronoi diagram]]s.]]		[[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 '''sweep line algorithm''' or '''plane sweep algorithm''' is an [[algorithmic paradigm]] that uses a conceptual ''sweep line'' or ''sweep surface'' to solve various problems in [[Euclidean space]]. It is one of the critical techniques in computational geometry.		In [[computational geometry]], a '''sweep line algorithm''' or '''plane sweep algorithm''' is an [[algorithmic paradigm]] that uses a conceptual ''sweep line'' or ''sweep surface'' to solve various problems in [[Euclidean space]]. It is one of the critical techniques in computational geometry.

OlliverWithDoubleL: math formatting

2023-02-27T06:47:22Z

math formatting

← Previous revision		Revision as of 06:47, 27 February 2023
Line 10:		Line 10:

	==Applications==		==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 ''N'' segments in the plane in time complexity of [[Big O notation\|O]](''N''~~ ~~log~~ ~~'' N'').<ref>{{citation		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'' log ''N'')}}.<ref>{{citation
	\| last1 = Shamos \| first1 = Michael I. \| author1-link = Michael Ian Shamos		\| last1 = Shamos \| first1 = Michael I. \| author1-link = Michael Ian Shamos
	\| last2 = Hoey \| first2 = Dan		\| last2 = Hoey \| first2 = Dan
Line 17:		Line 17:
	\| pages = 208–215		\| pages = 208–215
	\| title = Proc. 17th IEEE Symp. Foundations of Computer Science (FOCS '76)		\| 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 ''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		\| 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		\| last = Souvaine \| first = Diane \| author-link = Diane Souvaine
	\| title = Line Segment Intersection Using a Sweep Line Algorithm		\| title = Line Segment Intersection Using a Sweep Line Algorithm