In computational geometry, a sweep line algorithm or plane sweep algorithm is an

algorithmic paradigm An algorithmic paradigm or algorithm design paradigm is a generic model or framework which underlies the design of a class of algorithms. An algorithmic paradigm is an abstraction higher than the notion of an algorithm, just as an algorithm is an a ...

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, in Euclid's ''Elements'', it was the three-dimensional space of Euclidean geometry, but in modern mathematics there are ''Euclidean spaces ...

. It is one of the critical 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.

Applications

An application of the approach had led to a breakthrough in the

computational complexity In computer science, the computational complexity or simply complexity of an algorithm is the amount of resources required to run it. Particular focus is given to computation time (generally measured by the number of needed elementary operations ...

of geometric algorithms when 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 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.Donald ...

s) makes it possible to detect whether there are intersections among segments in the plane in

time complexity In theoretical computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations ...

of . The closely related Bentley–Ottmann algorithm uses a sweep line technique to report all intersections among any segments in the plane in time complexity of and space complexity of . 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 In mathematics, a Voronoi diagram is a partition of a plane into regions close to each of a given set of objects. It can be classified also as a tessellation. In the simplest case, these objects are just finitely many points in the plane (calle ...

( Fortune's algorithm) and the

Delaunay triangulation In computational geometry, a Delaunay triangulation or Delone triangulation of a set of points in the plane subdivides their convex hull into triangles whose circumcircles do not contain any of the points; that is, each circumcircle has its gen ...

or boolean operations on polygons.

Generalizations and extensions

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 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 (computational geometry), diameter of a set of points. The method ...

technique for designing geometric algorithms may also be interpreted as a form of the plane sweep, in the

projective dual In projective geometry, duality or plane duality is a formalization of the striking symmetry of the roles played by points and lines in the definitions and theorems of projective planes. There are two approaches to the subject of duality, one t ...

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 1976 in computing