the closest-pair-of-points algorithm

Given the coordinates of n cities on a map, which two are closest together? Checking every pair takes O(n^2) distance computations, which is wasteful when most pairs are obviously far apart. A divide-and-conquer algorithm finds the closest pair in O(n log n) by splitting the plane and being clever about the boundary, where the only pairs the recursion might miss can live.

Sort the points by x-coordinate and split them with a vertical line into a left half L and a right half R. Recursively find the closest pair within L (distance dL) and within R (distance dR); let d = min(dL, dR). The combine step must catch a pair with one point in L and one in R that is closer than d. The key geometric insight: any such pair must lie within distance d of the dividing line, so you only examine points in a vertical strip of width 2d around the line. Sort those strip points by y-coordinate; then a remarkable fact holds — each point need only be compared with a constant number (at most 7) of its following neighbors in y-order, because more than that many points within a d-by-2d region would force two of them closer than d, contradicting that d is the in-half minimum. So the combine step is O(n), and T(n) = 2 T(n/2) + O(n) = O(n log n).

Closest pair is a landmark of computational geometry: it shows divide and conquer extending naturally from one dimension to two, and it is one of the cleanest examples where a geometric bound (only a constant number of strip comparisons) is what rescues the combine step from being quadratic. The same strip-and-sweep idea reappears across geometry. The subtle, oft-cited detail is the constant-comparisons claim: it is not that the strip has few points, but that the d-spacing among them is so tight that each point can only have a few near-enough successors in the y-ordering.