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

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

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

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.

Applications

Application of this approach 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, and in particular, they described how a combination of the scanline approach with efficient data structures ( self-balancing binary search trees) 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 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 ( Fortune's algorithm) and the Delaunay triangulation or

boolean operations on polygons Boolean operations on polygons are a set of Boolean operations (AND, OR, NOT, XOR, ...) operating on one or more sets of polygons in computer graphics. These sets of operations are widely used in computer graphics, CAD, and in EDA (in integrated ci ...

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 technique for designing geometric algorithms may also be interpreted as a form of plane sweep, in the

projective dual In geometry, a striking feature of projective planes is the symmetry of the roles played by points and lines in the definitions and theorems, and (plane) duality is the formalization of this concept. There are two approaches to the subject of du ...

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