Sorting by x and recursing gives two candidate distances; the only pair the recursion can miss is one with a point on each side, and such a pair must lie within the smaller of those distances of the dividing line. Sorting that strip by y lets each point be compared with at most seven others, which is the classic bound. The lab measures the comparisons actually made and puts them beside 7n, and on twelve points the two are 5 and 84.
Core ideas
What the recursion can miss, why the strip is enough to catch it, and what the seven-neighbour bound is and is not.
Sort by x, split at the median, recurse on each half. A pair with both points on the same side was considered by that side's recursive call. So the only pair the recursion can have missed has one point on each side — and if its distance is less than d, the better of the two recursive answers, then both of its points are within d of the dividing line. That is the whole of the merge step's obligation.
Sort the strip by y. If two strip points are more than d apart in y they cannot beat d, so only a window matters. That window is a 2d-by-d rectangle, and it cannot contain more than eight points that are pairwise at least d apart — divide it into eight squares of side d/2 and note that two points in one such square would be closer than d. So each point needs at most seven comparisons, whatever the input.
On the lab's twelve points the strip comparisons total 5 against a bound of 7n = 84, and the busiest single strip ran at 4/5 = 0.80 comparisons per strip point. The bound is a worst case over every input; 4/5 is a measurement of one. A gap between them is not evidence that the proof is loose, and the page says so in the status line.
The material
The split, the merge obligation, the packing argument behind the seven, and the counts the lab measures against it.
Sort the points by x. If there are at most three, compare all pairs. Otherwise split at the median into L and R, recurse on each, and let d be the smaller of the two distances returned — held throughout as d², which is an integer. Form the strip: the points whose x is within d of the dividing coordinate, tested as (x − mid)² < d² so that nothing is rooted, and sorted by y. For each strip point, compare it with the following strip points until the y gap alone reaches d, again tested as (Δy)² ≥ d². Return the smallest distance seen.
If the closest pair has one point in L and one in R, then both lie within d of the dividing line, and in the strip sorted by y they are at most seven positions apart.
Let p ∈ L and q ∈ R be a pair at distance less than d. Then |px − qx| < d, and the dividing coordinate lies between px and qx, so each of them is within d of it. Both are therefore in the strip, and |py − qy| < d as well, so the scan's early exit on the y gap does not skip the pair.
For the position bound, consider the 2d-by-d rectangle centred on the dividing line and running from py to py + d. Every strip point between p and q in the y order lies in it. Cut the rectangle into eight squares of side d/2; the diagonal of such a square is d/√2 < d, so two points in one square would be closer than d, which contradicts d being the best distance within L and within R. Hence the rectangle holds at most eight points including p, so q is at most seven positions after it.
□
Read the second half of that proof carefully, because it is where the constant comes from and it is not an estimate. The eight squares are a packing argument: two points within one half-d square would violate the recursive guarantee, so there is at most one per square. The 7 is 8 − 1, and a different rectangle partition gives a slightly different constant — the literature has versions with 6 and with 4 — without changing the asymptotics at all.
The lab opens on twelve points running left to right, with (11, 4), (12, 5) and (13, 4) bunched together near the middle. The closest squared distance is 2, between (11, 4) and (12, 5) — and also between (12, 5) and (13, 4), so two pairs tie. The recursion made 17 comparisons; testing all 66 pairs gives the same answer. Five of those 17 were inside a strip, against a bound of 7n = 84.
It is worth being precise about where the winning pair was found, because the story about straddling pairs is easy to over-tell. Sorted by x, the top-level split is at x = 14 and the left half's split is at x = 11; (11, 4), (12, 5) and (13, 4) all land in the same three-point base case, and the pair is found by brute force there. The strip at the level above re-examines it and confirms it. So on this input the strip caught nothing the base cases had not already found — which is common, and is exactly why the strip cannot be dropped: nothing in the algorithm knows in advance that it was unnecessary here.
The lab's per-merge table gives, for each merge, the number of points, the size of the strip, and the comparisons made inside it. On the twelve points it reads: one merge with a strip of 2 making 1 comparison, one with a strip of 5 making 4, and the top-level merge with a strip of 2 making none. Total 5. The rightmost column is comparisons per strip point, as an exact fraction, and the largest is 4/5.
Beside it sits 7n = 84. Those two numbers are not the same kind of thing and the page labels them as such: 5 is a count of comparisons this run made, and 84 is a bound evaluated at n = 12. Their ratio is not a measure of anything, and in particular it is not a measure of how loose the proof is. The proof is about the worst input; this is one input.
17 comparisons against 66 is a real saving at n = 12 and it is a small one in absolute terms. The lab's five-point worked examples show the recursion doing 4 comparisons against 10, and its two-point example doing 1 against 1, where the recursion never happens at all. The crossover is where n log n falls below n(n − 1)/2, and at these sizes the constants matter more than the asymptotics.
The reason to build it anyway is the reason to build any of this: the bound is O(n log n) for every input, and the quadratic scan is Θ(n²) for every input. The lab runs both on the same points precisely because a recursion that drops a straddling pair returns a number that is real, plausible and too large, with no internal sign that anything went wrong.
Interactive
Divide and conquer against every pair, and the strip against 7n
Method
Recurse, then take seriously the one pair the recursion could not see.
The split needs the points in x order and re-sorting at every level would add a logarithmic factor. Sort once at the top and pass slices down; the strip needs a y order, which is a separate and much smaller sort.
The strip reaches d either side of the line, so it cannot be built until both recursive calls have returned. This is the step that makes the algorithm a merge rather than two independent computations.
For each strip point compare it with the following ones and break as soon as the y difference alone is at least d. Comparing backwards as well would double the work and find nothing new, and omitting the break is what turns a linear merge into a quadratic one on a strip that holds everything.
A recursion that drops a straddling pair returns a real distance between two real points. There is no invariant it violates and no assertion it fails. The only check is an independent enumeration, and the lab runs one on every redraw.
Sorted by x the points are (2, 9), (5, 1), (8, 14), (11, 4), (12, 5), (13, 4), (14, 12), (17, 2), (20, 10), (23, 6), (26, 15), (29, 3).
Twelve of the seventeen comparisons are in the four base cases, three each. The merges account for five, and the top-level merge for none at all: by the time it runs, d is 2, so the strip about x = 14 holds only points within √2 of it, which is two of them, and they are far enough apart in y that the scan breaks immediately.
The winning pair was found in a base case, not in a strip. That is worth stating plainly because the strip is usually introduced as the thing that finds the answer; its actual job is to make sure the answer cannot be missed. On this input it had nothing to find, and the algorithm has no way of knowing that in advance — which is why the merge runs regardless.
For a faded rehearsal, predict the whole table for the ten points in two columns at x = 0 and x = 1, which is another of the lab's worked examples. The supplied first move is that every point is within d of the dividing line there, so the strip at the top level holds all ten. Say how many comparisons the top-level merge then makes, and check whether the per-strip-point figure gets anywhere near seven.
You should be able to explain why only straddling pairs are at risk and why they lie in the strip, reproduce the packing argument that bounds the forward scan, read the per-merge table as measurements, and say why a measured count far below 7n says nothing about the tightness of the proof.
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.