How to Learn the Bentley–Ottmann Algorithm: Sweep Lines, Event Queues, Segment Intersections and Robust Geometry

Quick Read. Bentley–Ottmann finds all intersections among line segments without testing every pair. It sweeps an imaginary line across the plane, keeps the currently active segments in vertical order, and schedules only the endpoint and neighbour-crossing events that can change that order. The beginner should first understand segment intersection and sorting. The intermediate learner should trace the event queue and sweep-status structure. The advanced learner should understand why only neighbouring segments need to be tested and why the running time is output-sensitive. The professional should focus on degeneracies, exact predicates, duplicate events, numerical robustness and production geometry libraries.

One-sentence answer

Bentley–Ottmann turns a two-dimensional all-pairs intersection problem into an ordered sequence of local events, reporting k intersections among n segments in O((n+k) log n) time under the standard model.

Why this algorithm exists

If a drawing contains n line segments, the simplest intersection algorithm checks every pair. That requires n(n−1)/2 tests, so the work is Θ(n²) even when almost no segments cross. Bentley–Ottmann asks a better question: can we spend work roughly in proportion to the input plus the intersections that actually exist?

The key observation is geometric. Imagine a vertical line moving from left to right. At any x-coordinate, only the segments crossing that sweep line are relevant, and they have a definite top-to-bottom order. That order changes only at discrete events: a segment starts, a segment ends, or two neighbouring segments cross. Continuous geometry becomes an event-processing algorithm.

Level 1 — Beginner: master one segment-intersection test

Before learning the sweep, be able to decide whether two segments intersect. A standard foundation is the orientation predicate. For points a, b and c, the sign of the 2D cross product tells whether c lies to the left of, to the right of, or on the directed line from a to b.

orient(a,b,c) = sign((b.x-a.x)*(c.y-a.y)
                   - (b.y-a.y)*(c.x-a.x))

For general-position inputs, two segments ab and cd properly cross when c and d lie on opposite sides of ab and a and b lie on opposite sides of cd. Real software also has to handle collinearity, touching endpoints and overlapping segments.

The sweep-line picture

At a particular x-position, consider every segment that crosses the sweep line. Sort those segments by their y-coordinate at that x. This ordered set is called the sweep status. The algorithm also owns a priority queue of future events ordered from left to right.

Left endpoint event: a segment becomes active.
Right endpoint event: a segment stops being active.
Intersection event: two active neighbours exchange vertical order.

This is the first invariant to learn: immediately to the right of the current event, the sweep-status structure must represent the correct vertical ordering of all active segments.

Why only neighbours matter

Suppose two active segments are not adjacent in the sweep order. Another segment lies between them. They cannot become the next crossing pair until that separating segment moves out of the way through an endpoint or intersection event. Therefore the next undiscovered crossing can only arise between segments that are neighbours in the current status order.

This local-neighbour principle is the heart of Bentley–Ottmann. The algorithm avoids asking “which of all pairs intersect?” and instead asks “which adjacent pairs might become the next event?”

Level 2 — Intermediate: the two data structures

1. Event queue

The event queue is a priority queue ordered lexicographically by event point, typically x first and y as a tie-break. It begins with every segment endpoint. When neighbouring segments are found to intersect strictly ahead of the sweep, their intersection is inserted as a future event.

2. Sweep status

The status is an ordered set of active segments, commonly described using a balanced binary search tree. Its comparison key is not static: it represents the vertical order of segments at the current sweep position. Operations needed are insertion, deletion, predecessor, successor and local neighbour exchange.

while event_queue not empty:
    p = extract_next_event()

    process segments that start at p
    process segments that end at p
    process segments that cross at p

    update sweep-status order
    test newly adjacent pairs
    schedule valid intersections to the right

Walk through a crossing

Imagine segments A and B are adjacent, with A above B just before x = 5. They cross at x = 5. At that event the output records the crossing, then the status order is swapped so that B is above A immediately afterward. Only two new neighbour relationships can appear: B with the segment above it, and A with the segment below it. Those are the only new pairs that need intersection tests.

A good learning exercise is to draw five segments, write their endpoint events on paper and maintain the active ordering after every event. Do this before coding. The algorithm becomes much easier once the status invariant is visible.

Level 3 — Advanced: output-sensitive complexity

There are 2n endpoint events and, if all intersections are reported separately, k crossing events. Each event performs a constant number of balanced-tree and priority-queue operations costing O(log n), giving O((n+k) log n) time in the standard analysis. Space is O(n+k) in a straightforward implementation, although careful event management can avoid retaining stale events.

The phrase output-sensitive matters. If a dataset contains few crossings, the algorithm avoids the Θ(n²) cost of brute force. If the geometry genuinely contains Θ(n²) crossings, no reporting algorithm can avoid spending at least Θ(k) time just to emit them.

Correctness: a chain of local facts

Between consecutive event x-coordinates, the vertical order of active segments does not change.
A segment enters or leaves the order only at its endpoint.
Two segments can reverse their relative vertical order only by intersecting.
Immediately before their first crossing, two crossing segments must become adjacent in sweep order.
Therefore checking newly created neighbouring pairs is sufficient to discover every future crossing.
Processing events in left-to-right order ensures no valid event behind the sweep needs to be reconsidered.

These statements are more useful than memorising code. They let a learner reconstruct the algorithm and diagnose implementation errors.

The difficult part is degeneracy

Textbook explanations often assume general position: no vertical segments, no shared endpoints, no three segments meeting at one point and no overlapping collinear segments. Production data violates these assumptions. A professional implementation needs an explicit policy for every degenerate configuration.

Several endpoints may share the same x-coordinate.
An endpoint may lie in the interior of another segment.
Three or more segments may meet at one point.
Segments may be vertical.
Two segments may overlap over an interval instead of crossing at one point.
The same intersection may be discovered by more than one neighbouring relationship.

One robust strategy groups all events at the same geometric point and processes the sets of segments that start, end or pass through that point together. This avoids depending on an arbitrary event order for coincident geometry.

Numerical robustness is not optional

Floating-point rounding can make a geometry algorithm contradict itself: one comparison may say segment A is above B while another says the reverse. The classic Bentley–Ottmann sweep is particularly sensitive because its correctness depends on a consistent global event order and local geometric predicates.

For integer coordinates within a safe range, exact integer orientation tests are often possible with wider intermediate arithmetic. For general floating-point geometry, robust or adaptive exact predicates are preferable. Jonathan Shewchuk’s work on adaptive-precision predicates is a standard reference, and modern computational-geometry libraries such as CGAL package exact-predicate strategies rather than leaving every application to invent one.

Professional engineering choices

Define event identity: decide how coincident points and duplicate intersection events are canonicalised.
Avoid stale events: an intersection scheduled earlier may cease to be between neighbours; validate events when popped or support deletion.
Separate predicates from construction: deciding relative order robustly is different from computing a display coordinate for the intersection.
Use exact predicates where correctness matters: CAD, GIS, mesh repair and topology-sensitive pipelines should not rely on arbitrary epsilons.
Choose an output contract: report intersection points, intersecting pairs, split subsegments, or a full planar arrangement. These are different jobs.
Benchmark against the real geometry: sparse-road networks, dense line art and adversarial arrangements have very different k values and cache behaviour.

Testing ladder

Two disjoint segments.
Two segments crossing once.
Two segments touching at an endpoint.
Three segments crossing at one point.
Several vertical segments.
Collinear disjoint and overlapping cases.
A grid with many intersections.
Random short inputs compared against an O(n²) exact reference implementation.
Coordinates near numeric limits and nearly collinear triples.

The slow O(n²) method is extremely valuable as a test oracle. A professional algorithm engineer often keeps a deliberately simple implementation precisely so the faster sweep can be differential-tested on thousands of small random cases.

Common misconceptions

“The sweep line physically moves continuously.” The implementation jumps from event to event.
“Every active pair must be tested.” Only neighbouring pairs can create the next order change.
“O((n+k) log n) means the algorithm is always faster.” For tiny n, brute force may be simpler and faster.
“An epsilon fixes floating-point geometry.” A global epsilon can create inconsistent ordering and topology.
“Balanced tree comparison is just y-at-x.” Ties, vertical segments and exact event positions require a carefully defined comparator.

A learning route from beginner to professional

Beginner: implement orientation and an exact two-segment intersection test.
Intermediate: hand-trace a sweep using a sorted list before introducing a balanced tree.
Advanced: implement the event queue, neighbour scheduling and output-sensitive analysis.
Algorithm engineer: add grouped coincident events, stale-event validation and differential testing.
Professional: use robust predicates, define a precise arrangement/output contract, profile real datasets and compare against a mature geometry library.

For teaching, use a Predict–Run–Investigate–Modify–Make progression: predict which pair becomes adjacent next, run a small visual trace, investigate the invariant, modify one segment to create a new event order, then implement the sweep. Faded worked examples and Parsons-style ordering tasks can reduce syntax load while learners are still building the event-processing mental model.

Authoritative sources and further reading

J. L. Bentley and T. A. Ottmann, Algorithms for Reporting and Counting Geometric Intersections, IEEE Transactions on Computers, 1979.
J.-D. Boissonnat and F. P. Preparata, Robust Plane Sweep for Intersecting Segments, SIAM Journal on Computing.
CGAL 2D Intersection of Curves / Surface Sweep documentation, for a mature output-sensitive sweep framework.
J. R. Shewchuk, Adaptive Precision Floating-Point Arithmetic and Fast Robust Predicates.
S. Sentance, J. Waite and M. Kallia, Teachers’ Experiences of Using PRIMM to Teach Programming.
C. Szabo et al., Parsons Problems and Computing Education Learning Theories, Koli Calling 2025.

Closing idea. Bentley–Ottmann teaches a transferable algorithm-design pattern: replace a huge global search with a carefully maintained local order, identify the small set of events that can change that order, and do work only when the world actually changes.