Sweep line algorithm: Difference between revisions

Revision as of 15:30, 29 April 2010

Revision as of 15:32, 7 November 2012

Line 1:

[[Image:Fortunes-algorithm.gif‎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 a type of algorithm that uses a conceptual ''sweep line'' or ''sweep surface'' to solve various problems in Euclidean space. It is one of the key techniques in computational geometry.

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

==Applications==

Line 14:

| contribution = Geometric intersection problems

| doi = 10.1109/SFCS.1976.16

| pagepages = 208–215

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

| year = 1976}}.</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''&nbsp;+&nbsp;''K'')&nbsp;log&nbsp;''N'') and space complexity of O(''N'').<ref>{{citation

Line 29:

The [[rotating calipers]] technique for designing geometric algorithms may also be interpreted as a form of 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 sweeping approach may be generalised to higher dimensions.

==References==