In computational geometry

Computational geometry

Computational geometry is a branch of computer science devoted to the study of algorithms which can be stated in terms of geometry. Some purely geometrical problems arise out of the study of computational geometric algorithms, and such problems are also considered to be part of computational...

, 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 algorithms of rendering in computer graphics

Computer graphics

Computer graphics are graphics created using computers and, more generally, the representation and manipulation of image data by a computer with help from specialized software and hardware....

, followed by exploiting this approach in early algorithms of integrated circuit layout

Integrated circuit layout

Integrated circuit layout, also known IC layout, IC mask layout, or mask design, is the representation of an integrated circuit in terms of planar geometric shapes which correspond to the patterns of metal, oxide, or semiconductor layers that make up the components of the integrated circuit.When...

 design, in which geometric description of an IC was processed in parallel strips, because the entire description could not fit into memory.

Applications

Application of this approach led to a breakthrough in the computational complexity

Computational Complexity

Computational Complexity may refer to:*Computational complexity theory*Computational Complexity...

 of geometric algorithms when Shamos

Michael Ian Shamos

Michael Ian Shamos is an American mathematician, attorney, book author, journal editor, consultant and company director. He is Michael Ian Shamos (born April 21, 1947, and often referred to as Mike Shamos) is an American mathematician, attorney, book author, journal editor, consultant and company...

 and Hoey presented algorithms for line segment intersection

Line segment intersection

In computational geometry, the line segment intersection problem supplies a list of line segments in the plane and asks us to determine whether any two of them intersect, or cross....

 in the plane, and in particular, they described how a combination of the scanline approach with efficient data structures (self-balancing binary search tree

Self-balancing binary search tree

In computer science, a self-balancing binary search tree is any node based binary search tree that automatically keeps its height small in the face of arbitrary item insertions and deletions....

s) makes it possible to detect whether there are intersections among N segments in the plane in time complexity of O

Big O notation

In mathematics, big O notation is used to describe the limiting behavior of a function when the argument tends towards a particular value or infinity, usually in terms of simpler functions. It is a member of a larger family of notations that is called Landau notation, Bachmann-Landau notation, or...

(N log N). 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).

Since then, this approach has been used to design efficient algorithms for a number of problems, such as construction of the Voronoi diagram

Voronoi diagram

In mathematics, a Voronoi diagram is a special kind of decomposition of a given space, e.g., a metric space, determined by distances to a specified family of objects in the space...

 (Fortune's algorithm

Fortune's algorithm

Fortune's algorithm is a sweep line algorithm for generating a Voronoi diagram from a set of points in a plane using O time and O space...

) and the Delaunay triangulation

Delaunay triangulation

In mathematics and computational geometry, a Delaunay triangulation for a set P of points in a plane is a triangulation DT such that no point in P is inside the circumcircle of any triangle in DT. Delaunay triangulations maximize the minimum angle of all the angles of the triangles in the...

 or Boolean operations on polygons

Boolean operations on polygons

Boolean operations on polygons are a set of Boolean operations operating on one or more sets of polygons in computer graphics...

.

Generalizations and extensions

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

The rotating calipers

Rotating calipers

In computational geometry, rotating calipers is a method used to construct efficient algorithms for a number of problems.The method was first used by Michael Shamos in 1978 for determining all antipodal pairs of points and vertices on a convex polygon....

 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.