Bentley–Ottmann: Reporting All Crossings with a Sweep Line

The all-pairs intersection test from detecting segment intersections with orientation tests costs Θ(n²) regardless of how few segments actually cross. For n segments with k crossings, that is quadratic even when k is zero. A sweep line exploits the fact that a crossing is a local event in x: two segments can only cross if, at some x-coordinate, they are neighbours in the vertical order. Maintaining that order as the line advances turns the problem into a sequence of neighbour comparisons, and the total work becomes O((n + k) log n).

The algorithm is due to Bentley and Ottmann, published in 1979, and it is one of the clearest illustrations of the plane-sweep paradigm: a data structure that represents the state of the sweep, an event queue that schedules changes to that state, and an invariant that connects them. It is also, in its textbook form, an algorithm that assumes no two segments share an endpoint, no segment is vertical, and no three segments cross at one point. Every one of those assumptions is violated by real data, and repairing them is most of the engineering.

State and events

The sweep line is vertical and moves rightward. Two structures carry the state.

The status holds every segment currently intersecting the line, ordered by the y-coordinate of the intersection with the line. Because two straight segments can swap order at most once, this order is well defined between events and changes only at a crossing.

The event queue is a priority queue keyed on x, holding three kinds of event: a left endpoint, where a segment enters the status; a right endpoint, where it leaves; and an intersection point, where two segments in the status swap places. Endpoints are known in advance from the input. Intersections are discovered during the sweep, when two segments become neighbours, and are inserted into the queue at the x-coordinate where they will cross.

The invariant is that at any x between consecutive events, the status order matches the vertical order of the segments at that x. The sweep processes events in increasing x; between events, nothing about the order changes.

The three event handlers

At a left endpoint, insert the segment into the status at its correct y-position, find its immediate neighbours above and below, and test for intersection with each. Any crossing found is scheduled in the queue. Two new adjacencies have been created, and each is the only place a crossing between those particular segments could be detected.

At a right endpoint, remove the segment. Its former neighbours become adjacent to each other, so test that pair and schedule a crossing if one exists. Removing a segment can create exactly one new adjacency.

At an intersection event, the two segments are adjacent in the status by construction, and they swap positions. The pair immediately above and the pair immediately below are new adjacencies, so at most two new tests are performed. The crossing is reported.

The accounting is what makes the bound work: each event does O(1) neighbour tests, and each test is O(log n) for the status lookup plus O(1) for the predicate. There are O(n + k) events, since each crossing contributes one intersection event, so the total is O((n + k) log n). Every crossing is reported exactly once because it is scheduled only when the pair first becomes adjacent, and the queue entry is discarded if the two segments are no longer adjacent when it is popped.

import heapq

def sweep(segments):
    # Events: (x, kind, seq, payload) with kind 0 = left endpoint, 1 = intersection,
    # 2 = right endpoint, so equal x values order endpoints before crossings.
    # seq separates the payloads so the heap never compares a segment object.
    queue, seq = [], 0
    for s in segments:
        heapq.heappush(queue, (min(s.a[0], s.b[0]), 0, seq, s)); seq += 1
        heapq.heappush(queue, (max(s.a[0], s.b[0]), 2, seq, s)); seq += 1
    # The status is a stand-in for an ordered map keyed on y at the current
    # sweep x, with stable references so a segment can name its own neighbours:
    # insert, remove, seek pred/succ, and swap two adjacent entries.
    status, hits = OrderedMap(), []
    while queue:
        x, kind, _, item = heapq.heappop(queue)
        if kind == 0:
            status.insert(item, key=item.y_at(x))
            for nb in status.neighbours(item):
                schedule(queue, x, item, nb)      # push a crossing if one exists
        elif kind == 2:
            nb = status.neighbours(item)
            status.remove(item)
            if len(nb) == 2:
                schedule(queue, x, nb[0], nb[1])  # the new adjacency
        else:
            a, b = item
            if not status.adjacent(a, b):
                continue                          # stale event, drop it
            status.swap(a, b)
            hits.append((x, a.crossing_y(b)))
            for pair in status.new_adjacencies(a, b):
                schedule(queue, x, pair[0], pair[1])
    return hits

The schedule helper computes the crossing point and pushes it only if the two segments actually cross to the right of the current sweep position. The queue key is the crossing’s x, with the kind field breaking ties so endpoint events precede intersection events at the same x.

Why the queue needs a stale-event check

A scheduled intersection may never happen. Suppose segments a and b become adjacent at some x and are scheduled to cross at x = 10. Before the sweep reaches x = 10, a third segment c crosses a at x = 7, and the resulting swaps leave a and b non-adjacent. The event at x = 10 is still in the queue and must not be processed as a swap.

The standard guard is to re-check adjacency when the event is popped, and to drop the event if the two segments are not neighbours in the status. That check requires a way to locate each segment’s position in the status quickly, which is why the status is usually an ordered structure with parent pointers or a balanced tree with stable node references rather than an array whose indices shift on every insert.

An alternative is to compare the stored crossing point against the current sweep position and discard events that lie behind it. Both guards are cheap, and implementations usually carry both, because the adjacency check alone is sensitive to how the status reports neighbours at endpoints.

The general-position assumption and what breaks without it

The textbook proof relies on three properties that real inputs do not have.

Vertical segments. The status orders segments by their y at the current x, and a vertical segment has an entire range of y at a single x. It cannot be ordered against its neighbours without an arbitrary tie-break, and the tie-break must be consistent with the event order or the invariant fails. The usual fix is a symbolic shear: replace every x-coordinate by x + ε·y for a sufficiently small ε, which tilts the sweep line slightly and makes all segments non-vertical without changing any intersection’s existence. Implementations that cannot afford symbolic arithmetic instead handle vertical segments as a special case, inserting them as a block and testing all members against the neighbours of the block.

Shared endpoints. Two segments meeting at a common endpoint produce an intersection event at the same x as two endpoint events. The order in which the queue breaks ties determines whether the status is consistent when the intersection is processed. If the endpoint events are processed first, the segments are already in the status and adjacent; if the intersection is processed first, one of them may not be present. A total order on events, with endpoints before intersections at the same x and a fixed rule on y among endpoints, makes the sweep deterministic, but the rule must match the status comparison or the algorithm reports spurious crossings.

Multiple crossings at one point. If three segments pass through a single point, the pairwise swaps must be applied in an order that leaves the status in the correct final order. Naively processing two swaps and scheduling the third produces a transient state where the third pair is not adjacent and the crossing is missed. The fix is to collect all segments through the common point and reverse their block in the status, which requires detecting the coincidence in the first place.

None of these repairs is deep, but together they change the code from twenty lines of logic into a few hundred, and each one is a source of bugs that only appear on synthetic inputs. This is the gap between the published algorithm and a library implementation, and it is why a simpler structure with a worse bound is often the better engineering choice.

The lower bound, and how much the log factor costs

Reporting k crossings requires Ω(n log n + k) time in the algebraic decision-tree model: the n log n comes from the element-distinctness reduction, and the k is the output size. Bentley–Ottmann’s O((n + k) log n) has an extra log factor on the k term, because each reported crossing costs a heap operation. Chazelle and Edelsbrunner gave an algorithm attaining the O(n log n + k) bound, but it is substantially more complicated and is rarely implemented outside research code.

The log factor is not what decides between the two algorithms; the crossover depends on the density of crossings. When k is close to n², the sweep reports a quadratic number of events and the heap operations dominate, so its asymptotic advantage over a brute-force loop with a good bounding-box filter disappears. When k is small relative to n², which is the usual case for map data, circuit layouts, and collision broad-phase, the sweep’s advantage grows with n.

A hybrid is common: bucket the segments into a uniform grid, run the exact test within each cell and across adjacent cells, and accept the O(n²) worst case for adversarial distributions. It has no event queue, no degeneracy handling beyond the predicate itself, and it is cache-friendly. The sweep’s advantage is asymptotic, and asymptotic advantages only pay when the input is large enough to reach the asymptotic regime.

Where the sweep shows up elsewhere

The same state-and-events pattern produces the Voronoi diagram by Fortune’s sweep, where the status is a beach line of parabolic arcs and the events are site and circle events rather than endpoints and crossings. The trapezoidal map point location structure is built by a related sweep and answers queries in expected O(log n). Recognizing the pattern is more useful than memorising any single instance of it: a sweep is warranted when the answer depends on a local property of an ordering that changes only at discrete, enumerable events, and the cost of maintaining that ordering is logarithmic.