The idea: split, solve the halves, check the strip
Given n points in the plane, which two are closest? The closest pair problem shows up in collision checks, clustering and map data. The obvious method measures every pair. Divide and conquer does much less: cut the points in two with a vertical line, find the closest pair on each side, and then look only at a narrow strip around the line for a pair that crosses it.
The page names the points A, B, C, … from left to right, so a call on "A–H" means the first 8 points in x order. The recursion tree on the right shows each call: orange while it runs, green with its δ when it returns.
Brute force
Compare each point with every later point and keep the smallest distance. That is n(n − 1)/2 distance checks: 15 for 6 points, 120 for 16, about 500 000 for 1000. The work grows with n² (Demo: brute force on 16 points). Comparing squared distances avoids the square root; the page does that too, and its whole-number points make every comparison exact.
The recursion
- Sort the points by x once.
- Base case: with 3 points or fewer, compare every pair.
- Divide: split at the middle point. The split line sits half way between the last point on the left and the first on the right.
- Conquer: solve the left half and the right half. Let δ = min(δL, δR).
- Combine: look for a pair closer than δ with one end on each side, in the strip.
On 16 points the calls split 16 → 8 → 4 → 2, and the 8 calls of 2 points are base cases (Demo: divide and conquer on 6 points shows one split with two base cases of 3).
The strip check
A pair closer than δ that crosses the line has both ends less than δ from the line, because their x difference alone is less than δ. So only the points with |x − line| < δ matter. Sort them by y and walk up: compare each point only with the next ones whose y is less than δ above it, and stop at the first one that is δ or more higher. If a closer pair turns up, δ shrinks on the spot.
On the page's 16 points the halves give δL = 3.00 and δR = 3.16, so δ = 3.00. The strip around x = 12.5 holds G, I, H and J. The very first check, G with I, finds d = 2.24: the closest pair crosses the first split line, and neither half could have found it (Demo: 16 points, the closest pair crosses the split).
Why at most 7 checks per point
Take a point p in the strip. Every point it is compared with lies in the box above it: δ high and 2δ wide (δ on each side of the line). Cut that box into 8 squares of side δ/2, 4 on each side of the line. Two points in one square would be at most δ/√2 apart, which is less than δ, yet both are on the same side, where every pair is at least δ apart. So each square holds at most one point, the box holds at most 8 points including p, and p needs at most 7 checks.
In practice it is far fewer. In Demo: all 16 points in the strip the points sit close to the middle line, and at the top level every one of the 16 is in the strip. Still, the strip needs only 14 checks, never more than 2 from one point, because δ quickly drops to 2.00.
Running time
| Method | Checks on the page | Time |
|---|---|---|
| Brute force | 15 (6 points), 120 (16 points) | O(n²) |
| Divide and conquer, strip sorted each time | 8, 18 and 30 on the three sets | O(n log² n) |
| Divide and conquer, y order merged up the recursion | the same checks | O(n log n) |
Each level of the recursion does linear strip work, and there are log n levels: T(n) = 2T(n/2) + O(n), the same recurrence as merge sort (see the master theorem). Sorting the strip by y in every call adds a log factor; real code keeps the points in y order by merging the two halves' y lists on the way up, as merge sort does, and gets O(n log n). That is the best possible in the comparison model.
See also convex hull (another divide-and-conquer geometry algorithm), Karatsuba multiplication (divide and conquer on numbers), Delaunay triangulation (whose edges always include the closest pair) and k-d trees for nearest-neighbour queries.
What the page leaves out
The page uses at most 16 whole-number points with one unique closest pair and sorts each strip by y instead of merging y lists. Points with equal x are split by their index in x order (ties broken by y), which keeps the algorithm correct; the page does not show floating-point coordinates, randomized expected-linear-time methods (Rabin's grid algorithm), the sweep-line algorithm, closest pairs in 3 or more dimensions, or answering many nearest-neighbour queries with a k-d tree.
See where this page fits on the Recursion mind map.