Bentley–Ottmann Sweep Line

Bentley–Ottmann Sweep Line

Reporting every intersection among $n$ line segments appears to demand checking all $\binom{n}{2}$ pairs. Bentley–Ottmann avoids that quadratic scan by moving an imaginary vertical line from left to right and exploiting a local fact: the next intersection can occur only between segments that are adjacent along the sweep line. A priority queue tells us what happens next; an ordered status structure tells us which segments are currently neighbors.

This spotlight complements the broader sweep-line segment-intersection chapter. Here we concentrate on event machinery, correctness invariants, and engineering details hidden by the asymptotic bound.

Two coordinated views of the same motion

The algorithm maintains two structures:

• The event queue $Q$ is ordered lexicographically by $(x,y,\text{kind},\text{id})$. It initially contains every left and right endpoint; discovered crossings are inserted later.
• The status $T$ orders active segments by the $y$-coordinate at which they meet a conceptual line just to the right of the current event.

Call the lexicographically smaller endpoint of a segment its left endpoint, even for a vertical segment. A deterministic tie policy makes events reproducible, but production code should usually process all events at one geometric point as a batch.

At each endpoint event, a segment enters or leaves $T$. At a crossing event, the two participating segments reverse their vertical order. After any of those changes, only the newly formed neighboring pairs need inspection.

Reference pseudocode

The following Python-shaped pseudocode is intentionally not a drop-in geometry library. OrderedStatus, exact predicates, point batching, overlap handling, and robust event identity are substantial policies. The code exposes the control flow and the places where those policies attach.

def bentley_ottmann(segments):
    Q = EventHeap()              # key: (x, y, kind_rank, stable_id)
    T = OrderedStatus()          # order at x just right of current event
    scheduled = set()            # canonical (segment ids, point) keys
    output = []

    for s in segments:
        left, right = lexicographic_endpoints(s)
        Q.push(Event(left, "LEFT", s))
        Q.push(Event(right, "RIGHT", s))

    def schedule(a, b, current_point):
        if a is None or b is None:
            return
        hit = proper_intersection(a, b)  # one-point crossings only here
        if hit is not None and hit > current_point:  # lexicographic
            key = (min(a.id, b.id), max(a.id, b.id), hit)
            if key not in scheduled:
                scheduled.add(key)
                Q.push(Event(hit, "CROSS", a, b, key=key))

    while Q:
        e = Q.pop()
        T.set_sweep_position(e.point)  # conceptual x = e.x + epsilon

        if e.kind == "LEFT":
            T.insert(e.a)
            schedule(T.predecessor(e.a), e.a, e.point)
            schedule(e.a, T.successor(e.a), e.point)

        elif e.kind == "RIGHT":
            if not T.contains(e.a):
                continue
            below, above = T.predecessor(e.a), T.successor(e.a)
            T.remove(e.a)
            schedule(below, above, e.point)

        else:  # CROSS
            scheduled.discard(e.key)
            if not (T.contains(e.a) and T.contains(e.b)
                    and T.are_adjacent(e.a, e.b)):
                continue                    # stale event
            output.append(e.point)
            T.swap_adjacent(e.a, e.b)       # order immediately after crossing
            low, high = T.lower(e.a, e.b), T.higher(e.a, e.b)
            schedule(T.predecessor(low), low, e.point)
            schedule(high, T.successor(high), e.point)

    return output

Requiring hit > current_point prevents an event from rescheduling itself forever. Intersections equal to the current point belong in the current batch.

A compact event trace

Consider segments $A:(0,1)\to(8,7)$, $B:(0,6)\to(8,2)$, and $C:(3,0)\to(3,8)$. This example deliberately includes a vertical segment. The simplified trace assumes that all events at the same point are grouped and that status order is described immediately to the right of each event.

The vertical case reveals why “evaluate $y$ at $x+\varepsilon$” is shorthand, not literal floating-point code. A vertical segment meets the sweep line in an interval. Robust implementations treat geometry sharing an $x$—often a point—as a carefully ordered batch.

Why neighbor scheduling is enough

Suppose two active segments $a$ and $b$ cross at point $p$, and there is no earlier unprocessed event. Immediately before $p$, no third segment can lie strictly between $a$ and $b$ in the status order. If one did, that segment would have to leave the interval between them before $a$ and $b$ meet. Leaving requires either an endpoint or an intersection at an earlier position—an event the queue should already contain. Therefore $a$ and $b$ become adjacent before their crossing and their event is scheduled.

That is the core correctness lemma. Endpoint handlers preserve it by testing the pairs created around an insertion or deletion. A crossing handler preserves it by swapping the crossing pair and testing their new outside neighbors.

The comparator caveat

A balanced tree assumes its comparator stays fixed while elements are stored. A sweep status appears to violate that contract because “below at the current $x$” changes with $x$. Mathematically, relative order changes only at intersections, where the algorithm explicitly swaps adjacent segments. In software, mutating a global sweep_x used by a library comparator can invalidate tree invariants.

Production choices include a dedicated kinetic-order tree with explicit swaps; stable nodes/handles that avoid comparator-based lookup for deletion; or rebuilding at event batches, which is simpler but may sacrifice the target bound. Never use an epsilon offset as a universal robustness cure. Compare segment order with exact or adaptive orientation predicates, symbolic tie-breaking, and a documented policy for vertical and coincident geometry.

Stale events, duplicates, and simultaneous crossings

A crossing event may be valid when scheduled and obsolete when popped: another event can insert a segment between its pair, remove one participant, or cause the same geometric point to be discovered through another pair. The adjacency-and-membership check in the pseudocode safely discards such stale events. A canonical scheduled key prevents the same segment pair and point from filling the heap repeatedly.

Multiple segments may meet at one point. Pairwise events in arbitrary order can miss reports or cause contradictory swaps. A robust formulation pops a whole point $p$, partitions segments that start, end, or pass through $p$, reports incidences once, then reinserts continuing segments in their right-side order. Collinear overlaps are not isolated events; they need a separate interval policy.

Complexity—and what the bound assumes

There are $2n$ endpoint events and $k$ reported point intersections. Each queue insertion/removal and each status operation costs $O(\log n)$; each processed event performs only a constant number of them. Thus the standard bound is

$$O((n+k)\log n)$$

time and $O(n+k)$ queue/output space as commonly implemented (the active status itself is $O(n)$). The result is output-sensitive: if the arrangement truly has $\Theta(n^2)$ intersections, no reporting algorithm can avoid spending $\Omega(k)$ time merely to emit them.

The elegant bound is normally stated for nonvertical segments, no endpoint lying on another segment, no triple intersection, and no collinear overlaps. Real CAD, GIS, and mesh data violate all four assumptions. Before shipping, define whether endpoint touches count, whether duplicate segments are merged, how overlaps are represented, how coordinates are filtered or made exact, and whether output records points, segment pairs, or maximal overlap intervals. Bentley–Ottmann is a framework whose correctness depends as much on those contracts as on its heap and tree.