Given points in the plane, a direct closest-pair algorithm compares every pair. Divide and conquer can do less work: solve two halves, then examine only a narrow strip for a pair crossing the split. The strip can contain many points, so its width alone does not explain efficiency. A geometric separation argument is what limits the number of neighbors that each point needs to inspect.
The algorithm also has a data-order obligation. Points start sorted by x coordinate, but the strip must be inspected by y coordinate. Returning y-sorted lists from the recursive calls lets the combine step merge them in linear time. We will prove both the geometric and ordering claims, including equal x coordinates, coincident points and distance ties.
Specify points, distance and the returned witness
Definition 9.1.1
(A pair of distinct input occurrences)
Let the input be a finite sequence of integer-coordinate points . Distinct indices may have identical coordinates. For , squared Euclidean distance is
The function returns the minimum squared distance and the two original indices of a pair attaining it. If fewer than two points exist, it returns (None, None). A distance of zero is a legitimate optimum for two coincident input occurrences, not a missing-pair marker.
Any minimizing pair is acceptable. The implementation does not enumerate all tied pairs or promise the lexicographically smallest index pair.
Comparing squared distances is enough because square root is increasing on nonnegative numbers. Integer subtraction, squaring and addition keep these comparisons exact. The actual distance may be irrational; returning its square avoids introducing rounding just to choose a witness.
Sort records (x, y, original_id) once. Identical coordinates are adjacent, so a preliminary adjacent check can immediately return a zero-distance pair. After that case is removed, every recursive closest distance is positive. Split the sorted list by its middle index, so the two children have balanced sizes even when many x coordinates are equal.
Each recursive result carries its y-sorted points
A recursive call on an x-sorted list of at least two points returns three things: its minimum squared distance, a witness pair, and all its records sorted by (y, x, id). Two or three points are handled by direct pair comparisons. Larger calls split into left and right lists, solve both and merge their returned y-lists.
Let the child minimum distances be , and write . The current squared bound is . Let be the first x coordinate in the right list; all left x coordinates are at most , and all right x coordinates are at least .
Lemma 9.1.2
(The strip contains every improving cross pair)
Let be the smaller of the two child minimum distances and the first x coordinate of the right list. If a left point and a right point are at distance less than , then both lie in the strip .
Proof
(Horizontal separation is bounded by distance)
Suppose a left point and a right point are closer than . Their horizontal separation is no larger than their full distance, hence is less than . The split coordinate lies between their x coordinates, so each endpoint is less than from that line, and both belong to the strip . A pair outside the strip therefore cannot strictly improve the best child distance. Equal-distance cross pairs need not be found, because an already returned child pair witnesses that same value under the any-minimizer contract.
The code forms this strip by testing (x-c)**2 < best, using the initial child bound, and preserves the merged y-order. It does not calculate a floating-point width.
Why the next seven entries suffice
Within either recursive child, any two points are at least apart. Points from different children need not be: finding such a closer pair is the purpose of the combine step.
Lemma 9.1.3
(Seven later neighbors suffice)
Order the strip by . For a strip point , at most seven strip points after in this order have vertical gap .
Proof
(Four cells per child)
Fix a strip point . Only later y-ordered points with can form an improving pair with it. Consider that vertical band together with the strip. For each recursive child separately, its points lie in a region of width and height : the left child uses the left side of the cut, the right child the right side.
Divide each child's region into two columns and two rows. A cell has side lengths at most , so its diagonal is . Two points of the same child are at least apart, so each cell contains at most one point from that child. Four cells per child give at most eight points in the band, including . Consequently at most seven later strip entries have vertical gap less than . Points on the cut line are assigned to their actual recursive child, so equal x coordinates cause no ambiguity in this count, and cell boundaries can be assigned consistently to one cell. Earlier entries with the same y coordinate only use up some of those eight positions; they cannot increase the number after .
Proof X-ray
Why the count is eight and not unbounded
The proof has one geometric ingredient and one ordering ingredient. The geometric one is the cell side : its diagonal is below , which the separation inside a child forbids, so a cell holds at most one point of that child. The ordering one is the restriction to later entries with gap below , which confines the candidates to a band of height and so to two rows of cells. Without that restriction the strip can hold arbitrarily many points: put them all on the cut line, spaced apart vertically.
Points exactly on the cut line, and points on cell boundaries, need a convention rather than a new argument: each point is assigned to its actual child and each boundary to one cell, so the count of eight is not weakened by equal coordinates.
Thus compare each strip point with at most the next seven entries. If a later entry's squared vertical gap is already at least the current best squared distance, all still-later entries have at least that gap and can be skipped too.
The best value can decrease during the scan. The strip and seven-neighbor proof still use the original child bound : any later improvement also lies in that original strip and band. Testing against a smaller current vertical bound only discards pairs that cannot improve the new witness. Rebuilding the strip after every improvement is unnecessary.
Worked example 9.1.4
(A cross pair improves both child answers)
Use these input records, already in x order:
| Original ID | Point | Recursive side |
|---|---|---|
| Left | ||
| Left | ||
| Right | ||
| Right |
The left pair has squared distance ten, and the right pair twenty. Thus the initial squared bound is ten and the cut is . Only IDs 1 and 2 lie in the strict strip: their squared horizontal gaps are four and zero, while IDs 0 and 3 have gaps 25 and 16.
By y order the strip is ID 2 followed by ID 1. Their squared vertical gap is one, and their full squared distance is . The result is squared distance five with witness indices 1 and 2; its actual distance is .
Worked example 9.1.5
(Equal x coordinates and the balanced split)
Take the four points , all with . The index split puts IDs 0 and 1 on the left and IDs 2 and 3 on the right, with cut ; a split by x coordinate could not separate them. The child squared distances are and , so the bound is and the strip condition keeps all four points, already in y order. For ID 0 the next entry has squared vertical gap , so the scan breaks. For ID 1 the next entry, ID 2, has gap and squared distance , so the best becomes with witness , a pair that crosses the split. The next entry, ID 3, has gap , and the scan stops; the later points find nothing smaller. The result is squared distance , matching the smallest vertical gap . The strip holds every point, but each point inspects at most two later entries.
Worked example 9.1.6
(Coincident points are settled before recursion)
For the sorted records are . The first two are adjacent with equal coordinates, so the function returns squared distance and witness before any recursion. This case must be removed first: if , the strip condition selects nothing, and the packing argument, which uses cells of side and child points at least apart, has no content.
Counterexample mode
Taking only the better child answer misses the cross pair
For the worked four points, returning the smaller child answer would return ten. The true answer is five across the split. Recursion alone covers pairs within a side, so it cannot replace the strip argument.
Nor may points with equal x coordinates all be sent to one child: a purely coordinate-based split can become badly unbalanced. Splitting the sorted records by index preserves the balanced recurrence, while the geometric proof still permits equality at the cut.
Common mistake
(Treating zero distance as a missing pair)
A test such as if best: treats the legitimate optimum like the None returned for fewer than two points. Test best is None instead.
Common mistake
(Scanning the whole strip for every strip point)
The strip can contain every point, for example when all points lie on one vertical line with vertical gaps at least . Comparing each strip point with all later strip points would then take time. Only the next seven entries, with the early break on the vertical gap, need inspection.
An exact squared-distance implementation
Input points are pairs of integers, as type/shape preconditions; the function does not validate those conditions. It creates new records and does not reorder the caller's input. The inner routine is called only on lists of at least two points: larger calls split at size at least four, and smaller top-level inputs return beforehand.
def closest_pair_squared(points):
records = sorted((x, y, index) for index, (x, y) in enumerate(points))
if len(records) < 2:
return None, None
for index in range(1, len(records)):
if records[index][:2] == records[index - 1][:2]:
return 0, (records[index - 1][2], records[index][2])
def squared(p, q):
return (p[0] - q[0]) ** 2 + (p[1] - q[1]) ** 2
def by_y(p):
return p[1], p[0], p[2]
def solve(xs):
length = len(xs)
if length <= 3:
best = squared(xs[0], xs[1])
pair = (xs[0][2], xs[1][2])
for first in range(length):
for second in range(first + 1, length):
candidate = squared(xs[first], xs[second])
if candidate < best:
best = candidate
pair = (xs[first][2], xs[second][2])
return best, pair, sorted(xs, key=by_y)
middle = length // 2
cut_x = xs[middle][0]
left_best, left_pair, left_y = solve(xs[:middle])
right_best, right_pair, right_y = solve(xs[middle:])
if left_best <= right_best:
best, pair = left_best, left_pair
else:
best, pair = right_best, right_pair
y_order = []
left = right = 0
while left < len(left_y) and right < len(right_y):
if by_y(left_y[left]) <= by_y(right_y[right]):
y_order.append(left_y[left])
left += 1
else:
y_order.append(right_y[right])
right += 1
y_order.extend(left_y[left:])
y_order.extend(right_y[right:])
strip = [p for p in y_order if (p[0] - cut_x) ** 2 < best]
for first, p in enumerate(strip):
for second in range(first + 1, min(first + 8, len(strip))):
q = strip[second]
if (q[1] - p[1]) ** 2 >= best:
break
candidate = squared(p, q)
if candidate < best:
best = candidate
pair = (p[2], q[2])
return best, pair, y_order
best, pair, _ = solve(records)
return best, pair
For [(-4,0),(-1,1),(1,0),(5,2)], the result is (5, (2,1)); the reversed witness order is immaterial. With [(2,3),(9,0),(2,3)], it returns squared distance zero and indices 0 and 2. Vertical configurations need no slope or division, and equal-distance witnesses are handled by the stated any-minimizer contract.
Prove the recursive result as a whole
Proposition 9.1.7
(Correctness of the recursive combine)
After the preliminary check, for a list of records with pairwise different coordinates, the recursive routine returns the minimum squared distance, two original indices attaining it, and all the records sorted by .
Proof
(Induction over the recursion)
For two or three points, all pairs are explicitly checked and the returned y-order is sorted. Assume both child results are correct for a larger call. Their better answer is feasible in the parent, so it supplies an upper bound with a real witness.
Any parent pair is either within one child or crosses the split. A within-child pair cannot improve on that child's optimum. A cross pair that strictly improves the initial bound is in the strip by the strip lemma, and by the seven-neighbor lemma its later endpoint is among the next seven entries of its earlier endpoint. If it is pruned by the current y-gap bound, the current witness is already at least as good. Otherwise it is compared explicitly. Thus no pair is better than the final returned value, and that value is always witnessed by two input indices. Merging the child y-lists returns exactly the parent's records in y order.
Proof X-ray
Which facts the inductive step uses
The inductive step rests on four facts: the child answers (induction), the strip lemma, the seven-neighbor lemma, and the merge. The two prunings are safe for different reasons. The strict strip test discards pairs that cannot strictly improve the child bound; the break on the y-gap is valid because the list is sorted, so every later entry has at least that gap. The merge returns exactly the parent's y-list because merging two lists sorted by a total order, , gives the sorted union.
Both lemmas assume , which is why the preliminary duplicate check is part of the proof and not a speed-up. Without it, a zero child distance would make the strip empty and the argument would no longer cover cross pairs.
Preserve the linear combine step and account for memory
Merging the y-lists, building the strip and performing at most seven comparisons per strip entry all take work for one length- call. Balanced recursion therefore gives comparisons and arithmetic operations for , including the initial x sort.
Counterexample mode
Sorting the strip afresh adds another logarithmic factor
If every recursive level independently sorts its strip by y instead of carrying sorted y-lists upward, the combine step can cost . The recurrence becomes , giving as the resulting general bound.
The distance answer may still be correct. What changes is the justified runtime. Maintaining y order is part of the fast algorithm, rather than an incidental implementation detail.
The teaching implementation uses slices, merged lists and a strip list, so it does not have constant extra space. Peak storage is point-record references plus recursive frames: calls execute sequentially, and the sizes held along an active recursion path form a geometric series, with only constant-many lists proportional to each call's size. Total allocation across all calls is not the same as peak live memory.
These bounds count word-level operations and references. If coordinates have magnitude at most , squared distance is at most ; fixed-width implementations must accommodate intermediate differences, squares and sums. Python integers preserve exactness, but arbitrary-size integer arithmetic and comparisons have their bit costs. The geometric proof uses real only for reasoning; the program compares integer squares throughout.
Exercises and worked solutions
Quick check
(Recover the worked cross-pair improvement)
For the four worked points, give the two child squared distances, cut coordinate, strip order by original ID, and final squared distance. Why is the returned value five rather than its square root?
Solution · Answer
The child values are ten and twenty; the cut is . The strip's y order is IDs 2 then 1, and their squared distance is five. The interface returns a squared distance to preserve exact integer comparisons; the Euclidean distance is .
Quick check
(Justify seven using separation within each child)
How many small cells are used in each child's half-strip band, why can each contain at most one point from that child, and how does this limit the number after the current point?
Solution · Answer
Each child contributes four cells, two columns by two rows, each with diagonal . Two same-child points in one cell would contradict the child separation bound. There are at most eight points total including the current one, so at most seven later entries can have vertical gap below .
Quick check
(Handle equal coordinates without losing balance)
Why split by sorted-list index when many x coordinates coincide? What does the preliminary check return for [(2,3),(9,0),(2,3)], and why are indices 0 and 2 still a valid pair?
Solution · Answer
An index split keeps child sizes balanced even when a coordinate split would send almost everything to one side. The duplicate check returns squared distance zero with indices 0 and 2. They are different input occurrences despite identical locations, so they form a valid minimum pair.
Quick check
(Explain strict pruning under the witness contract)
Why may the strip omit points at horizontal distance exactly from the cut? Why may a y gap whose square equals the current best also be pruned? Would this code claim to enumerate every equal-distance minimizer?
Solution · Answer
Such a horizontal gap cannot belong to a cross pair strictly improving the child bound. Likewise a vertical gap already equal to the current distance cannot strictly improve it. An existing witness already attains that value, which is sufficient for any one minimizer. The code makes no all-minimizers or lexicographic-witness claim.
Quick check
(Keep the original packing bound when the answer improves)
If a strip comparison reduces the best squared distance, why is the original strip and next-seven limit still sufficient? What makes breaking on the current y-gap bound safe?
Solution · Answer
Every later improvement is also below the original child bound, so it lies in the original strip and original forward band, where there were at most seven later candidates. A smaller current y threshold can only remove pairs unable to beat the new witness. Later y values have no smaller gap, so once that bound fails the rest may be skipped.
Quick check
(Distinguish runtime and peak storage arguments)
Why does carrying y order upward avoid a second logarithmic factor? Does allocating several lists in each recursive call imply peak live storage here?
Solution · Answer
Merging two sorted child lists is linear; sorting them or the strip anew at every call can make the combine cost and the total bound . Peak storage is different: sequential recursion holds only constant-many size-proportional lists along a geometrically shrinking active path, totaling references, plus logarithmic frames. It is not constant-space, but cumulative allocation is not peak live memory.