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 Euclidean space is the fundamental space of geometry, intended to represent physical space. Originally, that is, in Euclid's ''Elements'', it was the three-dimensional space of Euclidean geometry, but in modern mathematics there are Euclidean ...

. 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 Scanline rendering (also scan line rendering and scan-line rendering) is an algorithm for visible surface determination, in 3D computer graphics, that works on a row-by-row basis rather than a polygon-by-polygon or pixel-by-pixel basis. All of t ...

s of rendering in

computer graphics Computer graphics deals with generating images with the aid of computers. Today, computer graphics is a core technology in digital photography, film, video games, cell phone and computer displays, and many specialized applications. A great de ...

, followed by exploiting this approach in early algorithms of

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

design, in which a 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 of geometric algorithms when Shamos and Hoey presented algorithms for

line segment intersection In geometry, an intersection is a point, line, or curve common to two or more objects (such as lines, curves, planes, and surfaces). The simplest case in Euclidean geometry is the line–line intersection between two distinct lines, which eithe ...

in the plane, and in particular, they described how a combination of the scanline approach with efficient data structures (

self-balancing binary search tree In computer science, a self-balancing binary search tree (BST) is any node-based binary search tree that automatically keeps its height (maximal number of levels below the root) small in the face of arbitrary item insertions and deletions.Donal ...

s) makes it possible to detect whether there are intersections among ''N'' segments in the plane in time complexity of O(''N'' log ''N''). The closely related

Bentley–Ottmann algorithm In computational geometry, the Bentley–Ottmann algorithm is a sweep line algorithm for listing all ''crossings'' in a set of line segments, i.e. it finds the ''intersection points'' (or, simply, ''intersections'') of line segments. It extends the ...

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 In mathematics, a Voronoi diagram is a partition of a plane into regions close to each of a given set of objects. In the simplest case, these objects are just finitely many points in the plane (called seeds, sites, or generators). For each seed ...

(

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(''n'' log ''n'') time and O(''n'') space. Section 7.2: Computing the Voronoi Diagram: pp.151–160. It was origina ...

) and the

Delaunay triangulation In mathematics and computational geometry, a Delaunay triangulation (also known as a Delone triangulation) for a given set P of discrete points in a general position is a triangulation DT(P) such that no point in P is inside the circumcircle o ...

or boolean operations on polygons.

Generalizations and extensions

Topological sweeping is a form of the plane sweep with a relaxed 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 In computational geometry, the method of rotating calipers is an algorithm design technique that can be used to solve optimization problems including finding the width or diameter of a set of points. The method is so named because the idea is an ...

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

{{Algorithmic paradigms Geometric algorithms