A Survey on the Variations of Plane Sweep Algorithms

INTRODUCE

Plane Sweeping is one of the most important approach to solve computational geometry problems. The common form of plane sweep is using a conceptual straight line or curve to sweep through the plane. The sweeping can be either linearly or rotationally depending on the types of the question we are facing. A number of actions are performed when the sweeping line meeting a certain set of events. This survey aims for an introduction of various types of plane sweep algorithms with examples. These include linear sweeping, rotational sweeping and topological sweeping. Some more recent development using the technique is also covered.

VERTICAL AND HORIZONTAL SWEEPING

In the most common form of plane sweep, a straight line is used as sweeping line, and the sweeping direction is linear. Sweeping in both directions are used in the Area of Rectangles Union problem.

are given a set of n axis aligned rectangles, whose edges are parallel to x or y axis, the goal is to find the overlapping area of the rectangles. We represent each rectangle by its lower-left point and upper-right point.

First, we do a vertical line sweep. The events are created when the sweep line encounters the vertical edges. Actions happen when the encountering happens. We know the edges are encountered when the lower-left point or upper-right point are encountered. We sort the events by x coordinates. The rectangle with its lower left point encountered is inserted into a set CURRENT.

Get Help With Your Essay
If you need assistance with writing your essay, our professional essay writing service is here to help!
Essay Writing Service

Similarly, the rectangle is removed from set CURRENT when its upper-right point is encountered. Thus, the set CURRENT only contains the rectangles with a sweep line going through them. The area swept at any moment is Δy * Δx. Δy is the overlapping distance of the sweep line and the rectangles. Δx is the distance of the two events created by the sweeping.

Then, we rotate the sweep line for 90° and do a similar sweeping from the bottom. The edges we consider are horizontal at this time. We use a variate c to represent the number of overlapping rectangles, we do c ← c+1 when a bottom edge is encountered, and c ← c-1 when a upper edge is encountered. When c becomes 0, we then find the length of the sweep line cut by the rectangles.

The time complexity is O(n2) if we use boolean array to store, but if we use data structures sch as BST, the total time can be reduced to O(nlogn).

ROTATIONAL SWEEPING

Besides vertical or horizontal Sweeping, algorithms that use rotational sweeping are often seem in computational geometry. We basically sweep through the plane with different slope of the sweep line. One of the classic examples of rotational sweeping is Rotating Calipers Algorithm.

The task is to Compute the diameter of a convex polygon. By diameter we mean the maximum distance between a pair of points in the polygon. The easiest way to think about it is to image that, we are using a real caliper to measure the diameter of the polygon. We would rotate the caliper to align with each edge of the polygon.

Geometrically, we make pairs of parallel lines tangent to the polygon. To sweep through the plane, we change the slope of the parallel lines until we cover 360 degrees. The parallel lines are kept tangent to the polygon at any slope given. At each iteration, the parallel lines will either be on at least a pair of vertices of the polygon, sometimes one or two of the line will overlap with the edges.

In this manner the two tangent points each make a single circuit of the polygon’s boundary. The diameter of the polygon is simply the maximum separation attained by the parallel lines during this sweep process.

a polygon with n vertices has O(n) antipodal pairs, so the time complexity of the sweep is O(n). The time complexity of the whole algorithm is O(nlogn) since to we need to presort the points.

TOPOLOGICAL SWEEPING
From the classes we learnt that it takes O(n2logn) for a vertical line to sweep through an arrangement. The good news is with topological sweeping, we can improve the time complexity to sweep through an arrangement to O(n2). 

Instead of sweep through the graph with a straight line, we sweep with a curve, the curve can be seen as a cut that intersects each line of the arrangement once.

At the beginning of the algorithm, we initialize a couple of data structure to help, which are a stack that contains all the vertices of the arrangement, the Upper Horizon Tree (UHT) and the Lower Horizon Tree (LHT).

An Upper Horizon Tree (UHT) is constructed as follow: We start from the left most cut, taking each edge of it (which means taking each edge that intersects the curve). When reached a vertex of the arrangement, take the higher edge out of it to the right and continue the same way until we pass the right-most vertex. The edges of the arrangement are traversed this way form the Upper Horizon Tree.

An iteration when building the Upper Horizon Tree, the blue edges are chosen next.

The Lower Horizon Tree (LHT) is basically the same thing in an opposite direction. We choose the lower edge every time we pass a vertex, until we pass the right most vertex.

An iteration when building the Lower Horizon Tree, the blue edges are chosen next.

The overview of the algorithm is as follow:

First, Sort all the lines in increasing order of slope.

Then construct the initial data-structures for the “left-most” cut. These data-structures are the Upper Horizon Tree, Lower Horizon Tree and the stack of vertices.

Start from the leftmost cut, choose an adjacent pair of cut edges with a common right end-point vertex v, and advance the cut past vertex v using in Upper Horizon Tree and Lower Horizon Tree. Repeat until the rightmost cut is reached. 

Step 1 takes O(nlogn) time for sorting, and the data structure can be constructed in O(n) time in step 2. There are O(n2) iterations each takes O(1) time in step 3, so the total time complexity is O(n2) for the whole algorithm.

RECENT DEVELOPMENT

Using plane sweep approach, many algorithm optimization and application can be done more efficiently. For example, a plane sweep algorithm for Parallel Interval Joins that outperforms the classic plane sweep approaches. Using plane sweep approach to solve the interval join problem was first introduced by F. P. Preparata and M. I. Shamos in 1985, and was optimized by D. Piatov, S. Helmer and A. Dignos in 2016.

In the Parallel Interval Joins problem, a set of parallel segments on a 1D space are given. The goal is to find all pairs of intervals that intersect.

The optimized approach is called Endpoint-Based Interval (EBI) Join. Firstly, we sort the intervals by their end points. More specifically, the intervals are sorted by their endpoint and secondarily by type, which flags whether the endpoint is a starting or an ending endpoint. Then do a left to right sweep with a vertical sweeping line, keeps track of active intervals, which started already but not finished. Active intervals are kept in a set ACTIVE. Similarly, the interval will be removed from the set ACTIVE if its endpoint is reached again. The active intervals of the opposite input collection are gone through and if there is overlapping detected, the corresponding active interval is added to the set Join. Join is the result we want when all the intervals are iterated.

Since each end points are recorded twice in the process, excluding sorting, there are 2*O(n) comparisons in total. Counting adding and removing the intervals based on their endpoints, if we use typical hash map to store the endpoints as interval index, the efficiency cost can be too high, since scanning through contents in hash map is slow. To solve this, the author uses a modified hash table called Gapless hash map.

Gasless hash map. Source: An Interval Join Optimized for Modern Hardware [1] 

There is a key, a value and a pointer for each chaining element in the hash table. There are also pointers to the elements that contain above information in the same bucket, and a pointer bucket prev to a hash table entry or an element. When the reference to an element is changed, the element’s position in the bucket is changed accordingly.

With this solution, we can use hash table as storing data structure in our approach, and take advantage of the O(1) time updating efficiency.

CONCLUSION

The plane sweep approach is useful in plenty of computational geometry algorithms. The variations of its forms can adapt into different scenarios flexibly. Furthermore, it turns some seemly difficult problems into approaches that are simple to achieve.

REFERENCES

[1] D. Piatov, S. Helmer, and A. Dignos. An Interval Join Optimized for Modern Hardware. In ICDE, 2016.

[2] Diane Souvaine, Heather Wong, Topological Sweep, Tufts University, April 2005

[3] Pirzadeh, Hormoz, Toussaint, Godfried T., Computational Geometry with the Rotating Calipers, Department of Computer Science, School of Computer Science McGill University, May 1999

[4] Herbert Edelsbuunner, Leondas J. Guibas, Topologically Sweeping an Arrangement, University of Illinois, Stanford University, November 1987

[5] Marc van Kreveld, Variations on Sweep Algorithms: efficient computation of extended viewsheds and class intervals, Dept. of Computer Science, Utrecht University

[6] F. P. Preparata and M. I. Shamos. Computational Geometry – An Introduction. Texts and Monographs in Computer Science. Spring, 1985.

[7] Panagiotis Bouros, Nikos Mamoulis, A Forward Scan based Plane Sweep Algorithm for Parallel Interval Joins, Department of Computer Science Aarhus University, Dept. of Computer Science & Engineering University of Ioannina, August 2017