A sweep line moves left to right over the endpoints, keeping a status list of the segments it currently crosses, and tests a new segment only against that list. On six spread-out segments that is 3 pair tests instead of 15. On four segments that all cross the middle of the picture it is 6 out of 6: the status list holds everything at once, and sorting the endpoints bought nothing at all. Both numbers are measured, and only one of them is what people remember.
Core ideas
The mechanism, the reason it can skip anything, and the input on which it skips nothing.
Two segments whose x ranges do not overlap are never on the sweep line at the same moment, and two segments that cross are both on the line at the crossing's x. So testing each new segment against the segments currently on the list cannot miss a crossing. That is the correctness argument, and it is completely independent of how much work it saves.
Each start event makes as many pair tests as there are segments already on the list. So the total is the sum over start events of the list size at that moment, which is exactly what the event table on the page displays column by column. On six spread-out segments the list never holds more than two, and the total is 3.
Put four segments so that all of them span the middle of the picture. The list reaches size four, every start event tests against everything before it, and the sweep makes 6 tests out of 6 possible. It has done every test the brute force would, plus a sort. That is not a flaw in the sweep: it is what its bound says, because the bound is about the output size as well as the input.
The material
The events, the correctness argument, the two measured counts, and the honest reading of the difference between them.
Given k segments, the events are their 2k endpoints sorted by x, each labelled as the start or the end of its segment. The sweep processes events in order, maintaining a status list of the segments whose start has been seen and whose end has not. On a start event the new segment is tested against every segment currently on the list; on an end event its segment is removed.
Every pair of segments that intersect is tested by the sweep.
Let segments A and B intersect at a point with abscissa x*. Both A and B have their start event at or before x* and their end event at or after it, since an intersection point lies on both segments and therefore inside both x ranges.
Consider whichever of the two has the later start event; say it is B. At the moment B's start event is processed, A has already started and has not yet ended, so A is on the status list. The start event for B therefore tests B against A. (Ties in x are broken so that start events precede end events at the same abscissa, which is what makes this argument hold when two segments share an endpoint.)
□
Notice what the proof does not claim: it does not say the sweep tests FEWER pairs, only that it tests enough of them. Those are separate questions, and the second one has an answer that depends on the input while the first does not. The lab checks the first by re-testing every pair on every redraw and comparing the two crossing sets.
Take (0, 0)–(8, 8), (0, 8)–(8, 0), (0, 4)–(8, 4) and (4, 0)–(4, 8): two diagonals, a horizontal and a vertical, all spanning the same square. The lab reports 4 segments, 8 events, 6 pair tests, 6 pairs there are, and 6 crossings found. The status list reaches size 4. The sweep did every test the brute force would do, and paid for a sort on top.
This is the preset that stops the saving being read as a bound, and it is worth dwelling on. Nothing has gone wrong: the algorithm is correct, the answer is right, and the crossing set matches the brute force exactly. What is absent is the improvement. The comparison in the status line reads “the sweep made every test the brute force would”, and it says so in amber rather than hiding it.
Six segments strung out along the x axis in three separated pairs give a very different picture. The lab reports 6 segments, 12 events, 3 pair tests against 15 pairs, and 3 crossings. Twelve pairs were skipped because their x ranges never overlapped, and no test could have found a crossing between two segments that are never on the line together.
Three tests against fifteen is a real saving and it is a measurement of those six segments. The general claim is different and weaker: the sweep does O((k + I) log k) work for k segments and I intersections, and when I is Θ(k²) — as in the four-segment bundle, where 6 of the 6 pairs cross — that is no better than quadratic. The bound is honest about this and the intuition usually is not.
A staircase of four segments, each ending where the next begins, has three shared endpoints. Do those count as crossings? This kit says yes: “meet” is the relation from the previous two lessons, and a shared endpoint is a shared point. The lab reports 3 crossings on that input and the brute force, using the parametric oracle, agrees. A different convention would be defensible and would have to be stated; what is not defensible is leaving it to the reader to find out.
That matters more than it sounds, because the status-list machinery makes it easy to get inconsistent: a sweep that skips the test when one segment's end event and another's start event share an abscissa will silently adopt a different convention from its own brute-force check. The lab's tie-break puts start events before end events at equal x, which is what keeps the two agreeing on the staircase.
Interactive
Pair tests the sweep line made, against every pair there is
Method
Count the tests, not the segments, and then look at the status list that produced the count.
The event count is always twice the segment count and tells you nothing about the work. What varies is how many segments each start event finds already on the list, and the sum of those is the figure to compare against k(k − 1)/2.
It is the single best predictor of whether the sweep helped. A list that never exceeds two on six segments means almost everything was skipped; a list that reaches k means nothing was.
Correctness and efficiency are separate claims and only one of them is in question here. The lab tests all k(k − 1)/2 pairs on every redraw and compares the two sets, so a sweep that skipped something it should not have would show as a set difference rather than as a smaller count.
Whether touching counts as crossing changes the answer on the staircase input and on any layout with abutting segments. Decide, write it down, and make sure the checking route uses the same convention — otherwise a disagreement between them is a disagreement about the question.
First the bundle: two diagonals, a horizontal and a vertical, all spanning the same square. Then six segments strung out in three separated pairs.
Read the bundle's size column downwards: 1, 2, 3, 4. The pair tests made at each start event are the size of the list it JOINED, so 0, 1, 2 and 3, and those sum to 6. There are 6 pairs. The arithmetic is not a coincidence — when every segment is on the list when every other one arrives, the sum telescopes to exactly k(k − 1)/2.
The other half of the picture is that the bundle also has 6 crossings. Every pair of those four segments really does cross, so the output is quadratic in the input, and a bound that is linear in the output size cannot be subquadratic here. The sweep is not failing to exploit structure; there is no structure to exploit.
For a faded rehearsal, predict the pair-test count for five segments all spanning the same interval, then for five segments in a diagonal staircase where each overlaps only its neighbour in x. The supplied first move is that the first is the telescoping sum again. Work out both, and then say what maximum status-list size each one reaches.
You should be able to build the event list and trace the status list, prove that no crossing can be skipped, compute the pair tests as a sum over start events, and state the bound in terms of both the input and the output size rather than the input alone.
Something to change about this lesson? Write it down, tick it off when it is handled, and export the list when you want to act on it. Kept in this browser only: nothing is sent anywhere, and nobody is notified.
No recommendations yet for this lesson.