Sweep (computer science)

Animation of a sweep algorithm that constructs a Voronoi diagram (algorithm from Fortune)

As Sweep, sweep method or sometimes scan method is a paradigm in computer science understood that the design of algorithms is applied. Such an algorithm is also called a sweep algorithm. The core of a two-dimensional sweep is the sweep line (sweep straight line) or the three-dimensional sweep plane (sweep plane). They “sweep out” the room, that is, move them through the entire room until all objects of the problem have been visited and processed. For this purpose, a data structure is used that stores the objects touched by the sweep line or plane. Such a data structure is then referred to as a sweep status structure . Problems of algorithmic geometry are solved particularly often . In general, a -dimensional static problem is converted into an (n-1) -dimensional dynamic problem in a sweep . ${\displaystyle n}$

Sweep algorithms

There are known and time-efficient sweep algorithms for solving the following two-dimensional problems:

• Determination of the intersection of line segments, time complexity ${\displaystyle {\mathcal {O}}((n+h)\log n)}$
• Construction of a Voronoi diagram , in time ${\displaystyle {\mathcal {O}}(n\log n)}$
• Intersection of two polygons, in -time, where k is the number of edge intersections of both polygons ${\displaystyle {\mathcal {O}}((n+k)\log n)}$
• Denseest pair of points in the plane, ${\displaystyle {\mathcal {O}}(n\log n)}$

literature

• Rolf Klein: Algorithmic Geometry. Springer Verlag (2005), ISBN 978-3-540-20956-0 .