Line Sweep Algorithms, in depth: events, status structures, tie-break order as correctness, skyline, sweep-and-prune and production pitfalls

Events, status and the invariant

Every sweep has three components, and writing them down before coding is the most useful habit in this area:

• Events. These are the points where the answer can change: interval starts and ends, rectangle edges, segment endpoints and, in Bentley-Ottmann, discovered intersections. Usually they are sorted once. When the sweep creates new events as it runs, they go in a priority queue.
• Status. This is what the sweep line currently crosses, kept in a form that answers the question you need. It can be a counter, a heap of active heights, a balanced tree of segments ordered by y, or a segment tree over compressed y coordinates.
• Invariant. This is a sentence that is true after every event, for example: count equals the number of intervals containing every point just to the right of the current x. If you cannot state the invariant, you cannot settle the tie cases, and the tie cases are where sweeps break.

The cost is the sort plus the sum of the status operations. A counter makes each event O(1). A heap or a balanced tree makes it O(log n). The sort dominates unless the input arrives already ordered, as time-stamped logs often do. In that case the sweep becomes a streaming algorithm with memory proportional to the number of active objects, not the total.

Ties decide correctness: maximum overlap

Take three meetings stored as half-open intervals: [9, 10), [10, 11) and [11, 12). No two overlap, so one room is enough. Sort the events by coordinate only, and the start of [10, 11) and the end of [9, 10) both sit at 10. If the start comes first, the count briefly reaches 2 and the program asks for a second room. That is a real bug which the code below reproduces. The correct order follows from the invariant. With half-open intervals, an interval no longer covers x = 10 when it ends there, so its end must be processed first. With closed intervals [s, e], the endpoint is covered, so starts must come first.

def max_overlap(intervals, half_open=True):
    """Max number of intervals covering one point, and the leftmost x where it occurs."""
    events = []
    for s, e in intervals:
        events.append((s, +1))
        events.append((e, -1))
    # at equal x: half-open [s, e) -> ends (-1) first; closed [s, e] -> starts first
    events.sort(key=lambda ev: (ev[0], ev[1] if half_open else -ev[1]))
    cur = best = 0
    best_x = None
    for x, delta in events:
        cur += delta
        if cur > best:
            best, best_x = cur, x
    return best, best_x

max_overlap([(9, 10), (10, 11), (11, 12)])                   # (1, 9)
max_overlap([(9, 10), (10, 11), (11, 12)], half_open=False)  # (2, 10)
max_overlap([(1, 5), (2, 6), (4, 8), (7, 9), (8, 10)])       # (3, 4)

Both answers to the meeting example are correct for their own semantics. If the calendar stores closed intervals, the meetings really do touch at 10. What is never correct is sorting by coordinate alone. The order then depends on how the sort handles ties and on the order of the input, so the same data can give different answers. Decide the semantics, write it in the sort key, and add a test with touching intervals.

A heap status: the skyline

The skyline problem takes buildings (left, right, height) and returns the outline as key points where the height changes. The events are the building edges. The status is the set of buildings the line currently crosses, and the question is "what is the tallest one?", so a max-heap fits. Removing an arbitrary element from a binary heap is awkward. The standard fix is lazy deletion: store each building's right edge alongside its height, and discard expired tops only when they reach the top.

import heapq

def skyline(buildings):
    events = []
    for l, r, h in buildings:
        events.append((l, -h, r))    # start: taller buildings first at equal x
        events.append((r, 0, 0))     # end marker: sorts after starts at equal x
    events.sort()
    out, live = [], [(0, float("inf"))]   # heap of (-height, right); ground never expires
    for x, negh, r in events:
        if negh:
            heapq.heappush(live, (negh, r))
        while live[0][1] <= x:            # lazy deletion: drop expired tops only
            heapq.heappop(live)
        h = -live[0][0]
        if not out or out[-1][1] != h:
            out.append((x, h))
    return out

On the input (2,9,10) (3,7,15) (5,12,12) (15,20,10) (19,24,8) it returns (2,10) (3,15) (7,12) (12,0) (15,10) (20,8) (24,0). Look at x = 7. The 15-high building ends, but the heap's top is checked against x only after the event, so it is dropped and the 12-high building shows through. The 10-high building from x = 2 is still in the heap below it. Expired entries buried deeper in the heap never matter, because only the top is ever read. The heap grows to at most n entries, so each event costs O(log n) amortised. This function was compared with a brute-force skyline, which evaluates the maximum height at every edge coordinate, on 2,000 random inputs, and they agreed on all of them.

Two tie rules are encoded in the tuple order. Starts sort before ends at equal x, so two adjacent buildings of the same height produce no dip to zero. Taller starts sort first, so a single x never emits two key points. Change either rule and you get a different output, which is a good mutation test for your own version.

Sweep-and-prune collision broadphase

Physics engines and spatial joins face the same all-pairs problem with boxes: which axis-aligned bounding boxes overlap? Sweep-and-prune sorts boxes by their minimum x and sweeps. The status is the list of boxes whose x-range is still open. A new box is tested on y only against those boxes, because only they can overlap it on x:

def sweep_and_prune(boxes):
    """boxes: (xmin, xmax, ymin, ymax). Returns overlapping index pairs (closed boxes)."""
    order = sorted(range(len(boxes)), key=lambda i: boxes[i][0])
    active, pairs = [], []
    for i in order:
        x0 = boxes[i][0]
        active = [j for j in active if boxes[j][1] >= x0]    # retire boxes that ended
        for j in active:
            if boxes[i][2] <= boxes[j][3] and boxes[j][2] <= boxes[i][3]:
                pairs.append((min(i, j), max(i, j)))
        active.append(i)
    return sorted(pairs)

With 2,000 boxes of side 10 scattered over a 1,000 by 1,000 square, brute force makes 1,999,000 pair tests. This sweep made 39,792 y-tests and found the same 762 overlapping pairs, about 50 times less narrow-phase work. It matched brute force on 500 random scenes. The benefit depends on the data. If every box spans most of the x-axis, the active list holds everything and the sweep falls back to O(n^2). Real engines therefore sweep the axis with the most spread, or use a grid or BVH instead. They also exploit temporal coherence: between frames the endpoint arrays are nearly sorted, so an insertion sort fixes them in close to linear time, and the swaps themselves report which pairs started or stopped overlapping.

Choosing the status structure

The table is the real decision you make. Segment-ordered trees are the hardest row. The order of segments along the sweep line changes at intersections, which is why Bentley-Ottmann needs a dynamic event queue and careful handling of degenerate cases. Coverage questions need coordinate compression and a segment tree, and the geometry segment tree article works through union area and perimeter. For closest pair, a sweep with an ordered set is an alternative to the divide-and-conquer method, with the same O(n log n) bound.

Operational guidance

• Normalise the representation first. Convert every interval to a single convention, half-open is usually best, and a single time zone or epoch unit before building events. Mixed conventions produce off-by-one overlaps that no tie rule can fix.
• Prefer integer or exact coordinates. Sweeps compare coordinates for equality to decide ties. Floating-point values that should be equal but differ in the last bit turn a touch into an overlap, or the reverse. Scale to integers where you can.
• Stream when the input is sorted. Logs, event streams and sorted files can be swept with memory proportional to the active set. For data larger than memory, use an external sort, then a single pass. That is how overlap joins in databases and genomics tools scale.
• Report positions, not only counts. When a maximum-overlap job alerts, the x where it happened and the active IDs make the alert actionable. Keep the IDs in the status when it is cheap.
• Test with adversarial ties. Include touching intervals, identical intervals, zero-length intervals and equal-height adjacent buildings, and compare against an O(n^2) brute force on random small inputs.

Failure modes

• Tie order left to the sort. This gives wrong room counts and phantom overlaps at shared endpoints, as the meeting example shows.
• Zero-length intervals. With half-open semantics, [5, 5) covers nothing, and with ends sorted first it never raises the count. With closed semantics it covers one point. Decide which behaviour you want and test it.
• Eager deletion from a heap. Searching the heap for the expired element costs O(n) per event. Lazy deletion keeps it logarithmic, but the heap can hold stale entries, so size memory by the total number of objects, not the active ones.
• Unbounded active sets. Sweep-and-prune on long, thin objects aligned with the sweep axis degrades to quadratic. Watch the size of the active list as a metric.
• Degenerate geometry in segment sweeps. Vertical segments, shared endpoints and three segments through one point break naive comparators. Use exact predicates.

Trade-offs

A sweep is the right tool when the problem has a natural order along one axis and the interactions are local in that order. It loses to other approaches in three situations. When objects are long relative to their spacing, the active set is large and a spatial grid or hierarchy prunes better. When queries arrive online against a changing set, an interval tree or R-tree answers each query without re-sweeping. When the dimension is high, sweeping one axis prunes almost nothing. In exchange the sweep offers simplicity, a sort plus a loop, and it works naturally as a streaming or external-memory pass. That makes it the default for batch jobs over time-ordered data.

What to do next

1. Write the invariant for your problem in one sentence, then derive the tie order from it and put it in the sort key.
2. Implement max_overlap with your production interval convention and add the touching meetings test.
3. Build a brute-force O(n^2) checker and compare on a few thousand random small inputs, always including duplicates and shared endpoints.
4. Pick the status structure from the table and record its worst case, such as active-set size, as a metric.
5. Work through the segment intersection sweep next. It is the case where the status order itself changes.