Sweep line

A sweep line turns a problem about a whole plane into a sequence of small updates. A vertical line moves from left to right and stops only where something changes. At each stop the program updates a small ordered list. This lesson uses it to answer “do any two of these n pieces meet?” in O(n log n) instead of checking all n²/2 pairs.

Sweeping

Every sweep has the same three parts:

• Events: the x values where something starts, ends or changes, sorted. Between two events nothing interesting happens, so the line jumps from event to event.
• The status: what the line currently crosses, kept in a structure that suits the question (a count, a heap, an ordered list).
• The invariant: a promise about the status that holds at every stop, and that makes the answer easy to read off.

Ties between events at the same x need a rule, chosen for the problem. Whether a piece that ends at x and one that starts at x count as meeting decides which comes first.

Sweeps you have met

• GRDY-3, the fewest platforms: events are arrivals and departures, the status is a count, and departures come first at equal times because the bookings are half-open.
• DVCQ-4, the closest pair: a sweep that keeps the recent points ordered by y finds it in O(n log n), as that lesson’s note said.
• DVCQ-P2, the skyline: events are the walls of buildings, and the status is the set of heights the line crosses.
• The area covered by many rectangles: events are their left and right sides, and the status is a segment tree over y (RNGQ-4) that knows how much of the line is covered.

Do any two pieces meet?

Michael Shamos and Dan Hoey (1976) used a sweep for this question. The status is the list of pieces the line crosses, ordered from the lowest to the highest at the line’s current x.

• Events: each piece starts at its left end and ends at its right end. Sort the events by x; at equal x, starts before ends (so pieces that touch at a shared end are both in the list at the same time), and starts from the lowest up.
• A start: find the new piece’s place in the list by its left end, and check it against its new neighbours, the piece just below and the piece just above. If its left end lies exactly on a piece in the list, those two meet.
• An end: remove the piece. The pieces that were just below and just above it are now neighbours: check them.
• Stop at the first check that finds two pieces that meet. If no check ever does, no two pieces meet.

Comparing heights needs no division: a point P is below a piece from A to B (with A to the left) exactly when cross(A, B, P) < 0. An upright piece is compared by its range of y. Step through the figure. In the first variant the crossing is found when a removal makes two pieces neighbours.

Why neighbours are enough

Let q be the meeting point furthest to the left (the lowest one, if several share that x), and let s and t be two pieces that meet at q. Left of q no two pieces meet, so up to q the list is in the right order: no two pieces swap places without crossing. Suppose a third piece u were between s and t in the list just before q. Close to q, s and t come together, so u would have to pass through q too, or cross s or t before q. Either way two pieces would meet at q or to its left, which goes against the choice of q, unless u ends before q. So once the pieces between s and t have ended, s and t are neighbours, and the event that made them neighbours (a start of s or t, or the removal of the last piece between them) checked them.

If s or t starts exactly at q, its left end lies on the other piece, and the search for its place in the list finds that (or the check with its neighbour does). Pieces that overlap along a line are found the same way: the later one starts on the earlier one.

Cost. 2n events, each with one search in the list and at most two checks. With a balanced search tree (BALT) as the list, each event is O(log n), so the sweep is O(n log n) after sorting.

The ordered list in Python

Python has no balanced search tree. A plain list works well in practice: find the place with your own binary search (the comparison depends on the line’s position, so bisect with a fixed key does not fit), then insert or pop. Those two move up to n references, which is O(n), but the move is a single fast copy in C, so tens of thousands of pieces are quick.

def below(p, t):                  # is point p below piece t at p's x?
    a, b = left[t], right[t]          # the ends, left one first
    if a[0] == b[0]:                  # an upright piece: compare y ranges
        return True if p[1] < a[1] else (False if p[1] > b[1] else None)
    c = cross(a, b, p)
    return None if c == 0 else c < 0  # None: p is on the piece

# a start of piece i: binary search its place by its left end
lo, hi = 0, len(active)
while lo < hi:
    mid = (lo + hi) // 2
    r = below(left[i], active[mid])
    if r is None:
        return (i, active[mid])       # the start lies on a piece
    if r:
        hi = mid
    else:
        lo = mid + 1
active.insert(lo, i)
# ... then check active[lo - 1] and active[lo + 1] against i

To remove a piece at its right end, find it the same way with its right end as the point (or with active.index(i), which is O(n) per removal and becomes slow for large inputs). Outside the practice pages, the sortedcontainers package gives a sorted list with fast inserts.

Every crossing, and other sweeps

• A line that turns: some problems sweep a ray around a point by angle instead of a line by x, for example to see which walls are visible from a spot.
• Time as the sweep: events in time order with a status that changes, as in simulations and in the scheduling problems of GRDY.
• Higher dimensions: a plane sweeping through space, with a 2-D sweep as its status, solves 3-D problems the same way.

Now try GEOM-P4, Any two tracks crossing?.