How Does the Closest-Pair-of-Points Algorithm Work?

The closest-pair problem asks: given $n$ points in the plane, which two are nearest under ordinary Euclidean distance? (Assume $n\ge2$; if $n<2$, no pair exists.) Checking every pair takes $O(n^2)$ time. A divide-and-conquer algorithm solves it in $O(n \log n)$ time by limiting how many points must be checked near each recursive split.

The method below assumes two-dimensional points and Euclidean distance. It returns any one closest pair if there are ties. If the points are in a different dimension or use a different distance measure, the details and running time may change.

The key idea

Sort the points by $x$-coordinate and divide the sorted list into two halves. Recursively find the closest pair in each half. Let $\delta$ be the smaller of those two distances.

A pair that is closer than $\delta$ cannot have both points in the same half; the recursive calls would already have found it. So a better pair, if one exists, must cross the dividing line. Both points must be within $\delta$ of that line, and their vertical separation must be less than $\delta$. This leaves only a narrow vertical strip to inspect.

Sort the strip by $y$-coordinate. For each point, it is enough to check the next seven points in that order, stopping sooner if the vertical gap exceeds $\delta$. The geometric reason is that a rectangle of width $2\delta$ and height $\delta$ can be divided into two $\delta$-by-$\delta$ regions, one on each side of the split. Each region can be subdivided into four squares of side $\delta/2$; each small square has diameter less than $\delta$, so it contains at most one point from that side. Thus at most eight points, including the point being considered, can occupy the relevant neighborhood.

Step-by-step algorithm

1. Sort the points by $x$-coordinate, and separately by $y$-coordinate. Give each point an identity so you can tell which half it belongs to even if several points have the same coordinates.
2. If a recursive subset has at most three points, check every pair directly.
3. Split the $x$-sorted list in half. Partition the $y$-sorted list into the same two groups, preserving its order.
4. Recursively find the closest pair in each half. Set $\delta$ to the smaller distance and keep that pair as the current best.
5. Collect, in $y$-order, the points whose horizontal distance from the dividing line is at most $\delta$. For each point, check the next seven points in this strip, or fewer if their vertical gap is greater than $\delta$. Update the best pair when you find a shorter distance.

A high-level version is:

ClosestPair(Px, Py):
    if size(Px) <= 3:
        return the closest pair found by checking every pair

    split Px into Lx and Rx
    split Py into Ly and Ry using point identities
    (leftPair, leftDistance) = ClosestPair(Lx, Ly)
    (rightPair, rightDistance) = ClosestPair(Rx, Ry)
    bestPair = the better of leftPair and rightPair
    delta = the smaller of leftDistance and rightDistance

    S = points in Py within delta of the dividing line
    for each point S[i], in y-order:
        compare it with the next at most 7 points in S
        stop when the y-gap exceeds delta
        update bestPair and delta if a shorter pair is found

    return bestPair

The strip is already in $y$-order because it is filtered from $P_y$. Preserving that order is essential: sorting the strip from scratch at every recursive call would add unnecessary work.

Worked example

Consider the points $A=(0,0)$, $B=(2,5)$, $C=(4,2)$, and $D=(6,6)$. The $x$-sorted order is $A,B,C,D$. Split it into $A,B$ and $C,D$.

The distance in the left half is

$$\begin{aligned} d(A,B) &= \sqrt{(2-0)^2+(5-0)^2} \\ &= \sqrt{29} \approx 5.39. \end{aligned}$$

The distance in the right half is

$$\begin{aligned} d(C,D) &= \sqrt{(6-4)^2+(6-2)^2} \\ &= \sqrt{20} \approx 4.47. \end{aligned}$$

So the current best distance is $\delta=\sqrt{20}$. The dividing line is between the halves, at $x=4$ for this example. The strip contains the points in $y$-order $A,C,B,D$. In particular, the algorithm checks $C$ and $B$ across the split:

$$d(B,C)=\sqrt{(4-2)^2+(2-5)^2}=\sqrt{13}\approx 3.61.$$

That is shorter than $\sqrt{20}$, so $B$ and $C$ are the closest pair. The strip check is what catches a pair that neither recursive call could find.

Why the running time is $O(n \log n)$

The two recursive calls each handle about half the points. At each level, splitting the $y$-ordered list and scanning the strip take $O(n)$ total work; each strip point causes at most seven comparisons. Therefore the recurrence is

$$T(n)=2T(n/2)+O(n),$$

which gives $T(n)=O(n\log n)$. The initial sorting also takes $O(n\log n)$, so it does not change the overall bound. Keep the points sorted by $y$ as the recursion proceeds rather than sorting anew at every level.

Common mistakes

• Checking only adjacent strip points: The closest cross-split pair need not be adjacent in $y$-order. Check up to the next seven points, stopping when the $y$-gap is too large.
• Sorting inside every recursive call: Re-sorting each subset by $y$ can lead to $O(n\log^2 n)$ time. Sort once, then filter the existing $y$-order at each split.
• Splitting only by coordinate when x-values tie: If points share the dividing $x$-coordinate, a coordinate test alone may assign them inconsistently. Divide by their positions in the $x$-sorted list and use point identities when partitioning the $y$-sorted list.
• Ignoring duplicate points: If two input points coincide, the minimum distance is zero. Detect duplicates up front and return that pair; otherwise the positive-distance strip argument applies.
• Comparing square roots unnecessarily: To find the minimum, compare squared distances such as $(x_1-x_2)^2+(y_1-y_2)^2$. Take a square root only if you need to report the distance itself.