Sweep line algorithm

As sweep, sweep method or sometimes scan method, a paradigm is understood in computer science, which has application in the design of algorithms. Such an algorithm is also called the sweep algorithm. The core of a two-dimensional sweep is the sweep -line (sweep - line) or in the three-dimensional plane, the sweep (sweep plane). By it, the space " swept ", that is, they are moved through the entire space to all objects of the problem has been viewed and processed. For this, a data structure is used for storing the touched by the sweep line or plane items. Such a data structure will be referred to as sweep status structure. Particularly often causes problems of computational geometry to be solved. Generally, a static dimensional problem is converted into an ( n-1) -dimensional dynamic problem in a sweep.

Sweep algorithms

For solving the following two-dimensional problems, there are known and time-efficient sweep algorithms:

• Determining the intersections of line segments that time complexity
• Construction of a Voronoi diagram in time
• The intersection of two polygons in time, where k is the number of edge points of intersection of the two polygons
• Densest pair of points in the plane