The brute-force wall, and one moving line
In guide 1 you learned to ask of two segments, 'do these cross?' using the orientation test. Now scale up: given n segments, which pairs cross? The obvious method tests every pair, which is n*(n-1)/2 tests — that is Theta(n^2) work whether one pair crosses or a million do. For 10,000 segments that is about 50 million orientation tests, and the count balloons as n grows. The painful part is how much of that work is obviously pointless: a segment in the top-left corner of the plane can never meet one in the bottom-right, yet brute force dutifully compares them anyway.
The sweep-line idea attacks exactly that waste. Picture a vertical line — call it the sweep line — that starts far to the left and glides steadily rightward across the whole picture. As it travels it passes over the geometric objects one moment at a time. The crucial insight is that two segments can only cross where the sweep line is touching both of them at once. So instead of comparing every far-flung pair, you only ever compare objects that the line is currently overlapping. The faraway top-left and bottom-right segments are never on the line together, so they are never compared. The whole game is to look only at the present, never at the irrelevant past or the un-reached future.
Two structures: an event queue and a status
Every line sweep is built from exactly two bookkeeping structures, and learning to spot them is most of the skill. The first is the event queue: the sorted timeline of those interesting moments, ordered by where the sweep line will be when each happens (usually by x-coordinate). For segment intersection the events are the left endpoint of each segment (where it enters the line's view), the right endpoint (where it leaves), and — discovered as we go — the crossing points themselves. The second is the status: a small record of exactly what the sweep line is touching right now, kept in an order that makes neighbours easy to find. For segments, the status holds the segments the line currently cuts through, sorted top-to-bottom by their height at the line's current x.
Why two structures and not one? Because they answer two different questions. The event queue answers 'what happens next, and where?' — it drives time forward. The status answers 'who is adjacent to whom right now?' — it tells you which pairs are even worth a crossing test. The deep payoff comes from a quiet geometric fact: two segments that cross must, at some x just before the crossing, become vertical neighbours in the status — there is no other segment squeezed between them at that instant. So you never have to test a pair that is not currently adjacent in the status. That is how an n^2 pile of pair tests collapses to a thin stream of neighbour tests.
Walking the segment sweep step by step
Let us run the Bentley-Ottmann sweep for segment intersection slowly, treating the status as a sorted list of segments stacked by height. The line moves right, pulling events off the queue in x-order. Each event is small and local: it inserts or removes one segment, or reports one crossing, and it only ever re-checks the handful of neighbours that just became adjacent. The orientation test from guide 1 is the workhorse inside every 'do these two actually cross?' question; the sweep's only job is to call it far fewer times.
- Left endpoint event: a new segment s enters. Insert s into the status at its correct height. Test s against only its immediate upper and lower neighbours — not the whole status. Any crossing you find with them gets scheduled as a future event in the queue.
- Right endpoint event: a segment s leaves. Remove s from the status. Its former upper and lower neighbours are now adjacent to each other, so test that newly-formed pair once — they may cross to the right of here.
- Crossing event: two segments swap their up/down order at this x. Report the intersection, swap them in the status, and test each against its NEW outer neighbour — the swap may have created two fresh adjacencies that could cross further right.
Trace a tiny case to feel it. Two segments A (gently rising) and B (gently falling) that cross once in the middle. The line meets A's left end, inserts A — no neighbours, nothing to test. It meets B's left end, inserts B just below A, tests the adjacent pair A,B, and finds they will cross; that crossing is queued. The line advances to the crossing event, reports it, and swaps A and B. They have no other neighbours, so nothing more is scheduled. Finally both right ends arrive and the segments leave. Total crossing tests done: a small handful, not a brute-force scan — and on this 2-segment example the win is invisible, but with thousands of segments scattered across the plane the same discipline keeps each segment talking only to its current neighbours.
Why it is fast — and the honest small print
Count the cost honestly. With n segments and k actual intersections, there are 2n endpoint events and k crossing events, so the queue handles O(n + k) events in total. Each event does a constant number of neighbour tests, but each one also inserts into, deletes from, or reorders the status — and to make those operations cheap the status must be a balanced search tree, where insert, delete, and find-neighbour each cost O(log n). The event queue is itself an ordered structure costing O(log(n + k)) per operation. Multiply events by per-event cost and you get O((n + k) log n) time. Compare that to brute force's flat Theta(n^2): when k is small — the common case where few segments actually cross — this is dramatically faster, essentially linearithmic rather than quadratic.
Now the honest small print, because asymptotics describe scaling, not a verdict at every size. First, the speedup is output-sensitive: it depends on k. In the pathological worst case every pair crosses, so k = Theta(n^2), and the sweep degrades to O(n^2 log n) — actually slower than brute force by a log factor, because all that tree machinery has overhead. The sweep wins when crossings are sparse, which is why you must know your inputs. Second, the elegant O((n+k) log n) bound assumes general position — no two events share an x-coordinate, no three segments meet at a point, no vertical segments. Real data violates all three, and the tie-breaking rules needed to handle those degeneracies are the genuinely fiddly part of a correct implementation, dwarfing the clean idea in code length.
One paradigm, many disguises
The reason sweeping deserves the grand word paradigm is that the very same event-queue-plus-status skeleton solves problems that look unrelated. The closest pair of points can be found with a left-to-right sweep whose status holds the points within the current best distance of the line, kept sorted by y; each new point only has to be checked against a constant number of nearby candidates, giving O(n log n) and matching the divide-and-conquer version from an earlier guide. Notice the status is no longer 'segments by height' — the skeleton stays, the contents change to fit the problem.
Interval problems are sweeps in disguise too, just on a one-dimensional line. Sort the interval endpoints, then sweep a point across them; the status is merely a counter of how many intervals are currently open. That single counter solves interval partitioning — the most rooms ever simultaneously busy is the running maximum of that counter — and it underpins the classic interval scheduling arguments by making 'what overlaps right now?' instantly answerable. Even rectangle-union area and the merging of overlapping ranges are sweeps where the status summarizes the cross-section the line currently cuts. Different status, same heartbeat: advance to the next event, update the small summary, read off the answer.
Step back and you can see the family resemblances to the rest of this rung. Like the orientation primitive, a sweep replaces vague visual reasoning with a finite, decidable list of cases. Like the convex-hull scans you just met, it leans hard on sorting first, then making a single disciplined pass. And the lesson generalizes: whenever a problem's answer changes only at a discrete set of moments and depends only on a small local neighbourhood, ask whether you can sort those moments into events and sweep. That instinct — turn a static two-dimensional mess into a moving one-dimensional timeline — is the real thing you take away, far more durable than any single algorithm's code.