Closest Pair of Points: A Divide-and-Conquer Algorithm in the Plane

1. Problem and Motivation

Given $n$ points in the two-dimensional plane, the closest pair problem asks: which two points are nearest each other under the ordinary (Euclidean) straight-line distance? The output is a pair of points and their distance — there is exactly one correct answer for the minimum distance, though several pairs may tie for it.

The obvious method compares every point against every other point. For $n$ points that means $\binom{n}{2} = \frac{n(n-1)}{2}$ distance checks — $\Theta(n^2)$ work. That is fine for a few hundred points, but it becomes impractical once $n$ reaches the tens or hundreds of thousands: a GIS system deduplicating map features, a physics simulation checking for near-collisions, or a clustering pipeline preparing nearest-neighbor structures cannot afford quadratic scans on every update. This lesson develops a divide-and-conquer algorithm that finds the closest pair in $O(n \log n)$ time — the same asymptotic cost as simply sorting the points.

The interesting difficulty is not the "divide" or the "recurse" steps — those are routine. It is the combine step: after solving the left half and the right half independently, the true closest pair might consist of one point from each half, straddling the dividing line. The entire algorithm's cleverness lives in checking that possibility without falling back to another $O(n^2)$ scan.

2. Prerequisites

This lesson assumes you are comfortable with:

• Recursion and divide-and-conquer, including recurrences and the recursion tree method (as in merge sort).
• Sorting points by a coordinate in $O(n \log n)$ time. See Fundamental Sorting Algorithms for the comparison sorts (merge sort, in particular) this lesson builds on directly — we will not re-derive sorting here, only reuse it.
• Basic coordinate geometry: plotting points, reading a Cartesian grid, and the Pythagorean theorem.

Note on naming: this is a distinct topic from the "closest pair to a target" one-dimensional two-pointer exercise covered elsewhere in this curriculum, which finds the pair in a sorted 1D array whose sum is nearest a target value. That is a different problem with a different technique; the shared word "closest" is coincidental, not a prerequisite relationship.

3. Terminology and Definitions

• Euclidean distance: for points $p=(p_x,p_y)$ and $q=(q_x,q_y)$, $\text{dist}(p,q) = \sqrt{(p_x-q_x)^2 + (p_y-q_y)^2}$. Implementations may compare squared distances to avoid the square root, but this lesson keeps actual distances for clarity.
• Dividing line: a vertical line $x = x_{\text{mid}}$ that splits the x-sorted points into a left half and a right half of (as close to) equal size.
• The strip: the set of points within horizontal distance $d$ of the dividing line, where $d$ is the best distance found so far from the two recursive halves. Only these points can possibly form a pair closer than $d$ that spans both halves.
• Degenerate / collinear inputs: inputs where three or more points lie on a common line, or where points coincide exactly (distance 0). The algorithm requires no special-casing for these — Euclidean distance and comparisons behave correctly — but they are worth testing explicitly (see Section 13).
• Coordinate and tolerance assumptions: this lesson uses exact (or double-precision) coordinates and exact comparisons. Production systems with noisy floating-point input often need an epsilon tolerance when comparing distances for "tie" detection; we note where that matters but do not build a tolerance system here.
• Boundary convention: a point exactly on the dividing line is treated as belonging to whichever half the split assigns it to (typically the left half, by array position) — it is not a special case, since the strip step re-examines it anyway if it lies within distance $d$ of the line.

4. A Concrete Example

The figure below plots exactly this example: all ten points, the dividing line, the shaded strip, and the winning pair.

5. Naive / Brute-Force Approach

The brute-force algorithm checks every pair of points once and keeps the minimum distance seen. It is short, obviously correct, and — importantly — it is not just a straw man here: the divide-and-conquer algorithm calls this exact routine as its base case once a recursive half shrinks to three or fewer points.

import math
from itertools import combinations

def closest_pair_brute_force(points):
    """Check every pair of points. O(n^2) time, O(1) extra space."""
    if len(points) < 2:
        raise ValueError("closest_pair_brute_force needs at least 2 points")
    best_pair = None
    best_dist = math.inf
    for p, q in combinations(points, 2):
        d = math.hypot(p[0] - q[0], p[1] - q[1])
        if d < best_dist:
            best_dist = d
            best_pair = (p, q)
    return best_pair, best_dist

if __name__ == "__main__":
    points = [(2, 3), (3, 8), (5, 4), (7, 9), (8, 2),
              (9, 7), (11, 3), (12, 8), (13, 2), (15, 6)]
    pair, distance = closest_pair_brute_force(points)
    print(f"Closest pair: {pair}, distance = {distance:.4f}")
    # Closest pair: ((11, 3), (13, 2)), distance = 2.2361

#include <cmath>
#include <cstdio>
#include <limits>
#include <stdexcept>
#include <utility>
#include <vector>

struct Point { double x, y; };

double distance(const Point& a, const Point& b) {
    double dx = a.x - b.x;
    double dy = a.y - b.y;
    return std::sqrt(dx * dx + dy * dy);
}

// Checks every pair of points. O(n^2) time, O(1) extra space.
std::pair<Point, Point> closestPairBruteForce(const std::vector<Point>& points, double& bestDist) {
    if (points.size() < 2) {
        throw std::invalid_argument("closestPairBruteForce needs at least 2 points");
    }
    bestDist = std::numeric_limits<double>::infinity();
    std::pair<Point, Point> bestPair{};
    for (std::size_t i = 0; i < points.size(); ++i) {
        for (std::size_t j = i + 1; j < points.size(); ++j) {
            double d = distance(points[i], points[j]);
            if (d < bestDist) {
                bestDist = d;
                bestPair = {points[i], points[j]};
            }
        }
    }
    return bestPair;
}

int main() {
    std::vector<Point> points = {
        {2, 3}, {3, 8}, {5, 4}, {7, 9}, {8, 2},
        {9, 7}, {11, 3}, {12, 8}, {13, 2}, {15, 6}
    };
    double bestDist;
    auto pair = closestPairBruteForce(points, bestDist);
    std::printf("Closest pair: (%.0f, %.0f)-(%.0f, %.0f), distance = %.4f\n",
                pair.first.x, pair.first.y, pair.second.x, pair.second.y, bestDist);
    // Closest pair: (11, 3)-(13, 2), distance = 2.2361
}

import java.util.List;

public class ClosestPairBruteForce {
    record Point(double x, double y) {}

    // Checks every pair of points. O(n^2) time, O(1) extra space.
    static double distance(Point a, Point b) {
        double dx = a.x() - b.x();
        double dy = a.y() - b.y();
        return Math.sqrt(dx * dx + dy * dy);
    }

    static Point[] closestPair(List<Point> points) {
        if (points.size() < 2) {
            throw new IllegalArgumentException("closestPair needs at least 2 points");
        }
        double bestDist = Double.POSITIVE_INFINITY;
        Point[] bestPair = new Point[2];
        for (int i = 0; i < points.size(); i++) {
            for (int j = i + 1; j < points.size(); j++) {
                double d = distance(points.get(i), points.get(j));
                if (d < bestDist) {
                    bestDist = d;
                    bestPair[0] = points.get(i);
                    bestPair[1] = points.get(j);
                }
            }
        }
        return bestPair;
    }

    public static void main(String[] args) {
        List<Point> points = List.of(
            new Point(2, 3), new Point(3, 8), new Point(5, 4), new Point(7, 9), new Point(8, 2),
            new Point(9, 7), new Point(11, 3), new Point(12, 8), new Point(13, 2), new Point(15, 6)
        );
        Point[] pair = closestPair(points);
        double d = distance(pair[0], pair[1]);
        System.out.printf("Closest pair: %s-%s, distance = %.4f%n", pair[0], pair[1], d);
        // Closest pair: Point[x=11.0, y=3.0]-Point[x=13.0, y=2.0], distance = 2.2361
    }
}

6. Limitation of Brute Force

Brute force performs $\binom{n}{2} = \Theta(n^2)$ distance computations. At $n=10{,}000$ points that is roughly 50 million checks — survivable on modern hardware, but at $n=1{,}000{,}000$ it becomes 500 billion, which is no longer a per-request operation. Nothing about the brute-force method reuses information between comparisons: knowing that point $P$ is far from point $Q$ tells you nothing about $P$ versus $R$. The divide-and-conquer method fixes exactly this by discarding, at each level, all pairs that provably cannot be the closest pair once a candidate distance $d$ is known.

7. Core Insight

Why does the strip need to be sorted by y rather than reused in x-order? Because two points that straddle the dividing line are automatically close in the x-direction (both within $d$ of the line, so at most $2d$ apart in x) — the only remaining question is whether they are also close in y. Sorting by y turns "search all pairs in the strip" into "look at your neighbors in a short sorted list," which is what makes the combine step fast.

8. Plain-English Steps and Pseudocode

1. Sort all $n$ points by x-coordinate once, before any recursion.
2. If three or fewer points remain, solve directly with brute force (Section 5) and return.
3. Otherwise split the x-sorted points at the midpoint into a left half and a right half.
4. Recursively find the closest pair (and its distance) in the left half, and separately in the right half.
5. Let $d$ be the smaller of the two halves' distances, and keep that half's pair as the current best.
6. Build the strip: every point (from either half) whose x-coordinate is within $d$ of the dividing line.
7. Sort the strip by y-coordinate.
8. Scan the y-sorted strip; for each point, compare it only against subsequent points whose y-coordinate is still within $d$ — stop as soon as the y-gap reaches $d$.
9. If any strip comparison beats the current best distance, replace the best pair and distance.
10. Return the best pair and distance found.

Pseudocode

closestPair(points):
    Px = sort(points, key = x-coordinate)
    return closestPairRec(Px)

closestPairRec(Px):
    n = length(Px)
    if n <= 3:
        return bruteForce(Px)

    mid = n / 2
    xMid = Px[mid].x
    Left  = Px[0 .. mid-1]
    Right = Px[mid .. n-1]

    (pairL, dL) = closestPairRec(Left)
    (pairR, dR) = closestPairRec(Right)

    if dL <= dR:
        (bestPair, d) = (pairL, dL)
    else:
        (bestPair, d) = (pairR, dR)

    strip = [ p in Px if |p.x - xMid| < d ]
    sort strip by y-coordinate

    for i in 0 .. length(strip) - 1:
        j = i + 1
        while j < length(strip) and (strip[j].y - strip[i].y) < d:
            dist = distance(strip[i], strip[j])
            if dist < d:
                d = dist
                bestPair = (strip[i], strip[j])
            j = j + 1

    return (bestPair, d)

flowchart TD
    A["Input: n points in the plane"] --> B["Sort all points by x-coordinate (once, upfront)"]
    B --> C{"n <= 3?"}
    C -- "yes" --> D["Brute-force check all pairs"]
    C -- "no" --> E["Split at median x into Left and Right halves"]
    E --> F["Recurse: closestPair(Left)"]
    E --> G["Recurse: closestPair(Right)"]
    F --> H["d = min(dLeft, dRight)"]
    G --> H
    H --> I["Build strip: points with |x - xMid| < d"]
    I --> J["Sort strip by y-coordinate"]
    J --> K["Scan strip; compare each point only to the next few in y-order"]
    K --> L{"Closer cross-boundary pair found?"}
    L -- "yes" --> M["New best pair from the strip"]
    L -- "no" --> N["Keep the half's best pair"]
    D --> O["Return closest pair and distance"]
    M --> O
    N --> O
                

9. Manual Trace

Continuing the worked example from Section 4 (points A–J, dividing line $x_{\text{mid}}=8.5$, $d=\sqrt5\approx2.236$ from the right half's pair G–I):

Building the strip. Keep only points with $|x-8.5| < 2.236$, i.e. $x \in (6.264,\,10.736)$:

The strip is exactly $\{D, E, F\}$ — two points from the left half (D, E) and one from the right half (F), which is precisely the cross-boundary candidate set the algorithm needs to check.

Sorting the strip by y: E $(y=2)$, F $(y=7)$, D $(y=9)$.

Scanning:

• E vs F: $\Delta y = 7-2=5$. Since $5 \ge d(2.236)$, the scan stops here for E — no other strip point can be closer to E in y either, since the strip is y-sorted.
• F vs D: $\Delta y = 9-7=2 < d(2.236)$, so compute the real distance: $\text{dist}(F,D)=\sqrt{(9-7)^2+(7-9)^2}=\sqrt{4+4}=\sqrt8\approx2.828$. That is larger than $d\approx2.236$, so it does not replace the current best.
• D has no points after it in the sorted strip.

No strip comparison beats $d$, so the answer stands: G(11,3)–I(13,2), distance $\sqrt5\approx2.236$ — matching the brute-force answer over all ten points (verified in Section 13/Implementation testing).

10. Correctness Reasoning

Two things must be proven: that recursing on halves is safe (routine structural induction: each half's recursive result is correct by the inductive hypothesis, and the true global closest pair is either fully inside one half or straddles the line), and the interesting part — that the strip scan, which compares each point to only a bounded number of y-neighbors, cannot miss a closer straddling pair. That second part rests on a packing (pigeonhole) argument.

Setup. Let $d = \min(d_L, d_R)$ be the best distance from the two recursive halves, so every pair of points within the same half is at distance $\ge d$ from each other (that is what "closest pair in that half is $d_L$ (or $d_R$)" means, and $d\le d_L$ and $d\le d_R$). Suppose some point $p$ in the strip could possibly be closer than $d$ to another strip point $q$. Then $q$ must have $|p.y - q.y| < d$ (otherwise the straight-line distance already exceeds $d$), so it suffices to bound how many strip points can lie within $d$ of $p$ in the y-direction.

The box. Consider the axis-aligned rectangle of width $2d$ (spanning $d$ to the left and $d$ to the right of the dividing line — exactly the strip's width) and height $d$ (the y-range in which a point could still be closer than $d$ to $p$). Partition this $d \times 2d$ rectangle into 8 congruent cells, each of size $\frac{d}{2} \times \frac{d}{2}$: four columns of width $\frac d2$ across the $2d$ width, and two rows of height $\frac d2$ across the $d$ height.

One point per half per cell. Any two points that fall inside the same $\frac d2 \times \frac d2$ cell are at most a cell-diagonal apart: $\sqrt{\left(\frac d2\right)^2+\left(\frac d2\right)^2} = \frac{d}{\sqrt2} \approx 0.707d$, which is strictly less than $d$. But two points from the same half (both left, or both right) are guaranteed to be at distance $\ge d$ from each other — that is exactly what "$d$ is that half's closest-pair distance" means. So two same-half points cannot share a cell. Since each half occupies exactly 2 of the 4 columns (the left two columns lie in the left half, at $x\lt x_{\text{mid}}$; the right two lie in the right half), each half touches $2\times2=4$ cells, and each of those 4 cells can hold at most one point from that half.

Because the scan checks every strip point against every "still-within-$d$" neighbor that follows it in y-order, and the packing bound guarantees that set is never larger than 7, no closer straddling pair can be missed. Combined with the inductive correctness of the two recursive halves, the whole algorithm is correct: it returns the true global closest pair.

11. Complexity Analysis

Splitting into two halves of size $n/2$ and recursing costs $2T(n/2)$. The combine step — computing $d$, filtering the strip, and scanning it — touches each of the $n$ points a bounded number of times, so it costs $O(n)$ if the strip can be produced already sorted by y without an extra sort, or $O(n\log n)$ if the strip is re-sorted by y from scratch at every level. Either way, the recurrence is:

The recursion tree has $\log_2 n$ levels; the top level does $O(n)$ combine work, the next level does two subproblems each doing $O(n/2)$ combine work (totaling $O(n)$ again), and so on — $O(n)$ work per level across $O(\log n)$ levels gives $O(n\log n)$ total, on top of the one-time $O(n\log n)$ upfront sort by x. Recursion depth is $O(\log n)$, so stack usage is modest even for very large $n$; an iterative bottom-up rewrite is possible if extremely deep recursion is a concern, but it is rarely necessary at realistic input sizes.

There are two implementation choices for the strip's per-level sort, with different constants:

• Re-sort the strip by y at every level (the version implemented in Section 12): each level's strip sort costs $O(n\log n)$, and with $O(\log n)$ levels the total becomes $O(n\log^2 n)$. This is slightly worse asymptotically than optimal, but it is simple, easy to verify, and fast enough in practice for the overwhelming majority of workloads.
• Carry a y-sorted auxiliary array through the recursion, merging it the same way merge sort merges its two halves: instead of re-sorting from scratch, merge the left half's y-sorted array with the right half's y-sorted array in $O(n)$ time, then filter that already-sorted array down to the strip in $O(n)$ time. This removes the extra $\log n$ factor from the combine step, giving the fully optimal $T(n)=2T(n/2)+O(n)=O(n\log n)$.

Both versions do the same $O(n\log n)$ initial sort by x; the difference is only in how the per-level y-ordering is maintained. Section 12 implements and verifies the simpler $O(n\log^2 n)$ version and states this choice explicitly in its code comments.

12. Implementation

The implementation below is the $O(n\log^2 n)$ version that re-sorts the strip by y-coordinate at every recursion level (the second bullet in Section 11 describes the further $O(n\log n)$ optimization as a note, without implementing it, so the code here stays straightforward to read and to verify by hand). All three languages were executed against the worked example and against 200 randomized stress tests comparing this implementation's output to the brute-force implementation from Section 5; every trial agreed exactly (see Section 13).

import math
from itertools import combinations

def _brute_force(points):
    best_pair = None
    best_dist = math.inf
    for p, q in combinations(points, 2):
        d = math.hypot(p[0] - q[0], p[1] - q[1])
        if d < best_dist:
            best_dist = d
            best_pair = (p, q)
    return best_pair, best_dist

def _closest_in_strip(strip, d, best_pair):
    # Re-sorting the strip by y at every level costs O(n log n) per level,
    # giving O(n log^2 n) overall -- simpler to verify than the fully linear version.
    strip = sorted(strip, key=lambda p: p[1])
    for i in range(len(strip)):
        j = i + 1
        while j < len(strip) and (strip[j][1] - strip[i][1]) < d:
            dd = math.hypot(strip[i][0] - strip[j][0], strip[i][1] - strip[j][1])
            if dd < d:
                d = dd
                best_pair = (strip[i], strip[j])
            j += 1
    return best_pair, d

def _closest_pair_rec(points_sorted_by_x):
    n = len(points_sorted_by_x)
    if n <= 3:
        return _brute_force(points_sorted_by_x)

    mid = n // 2
    x_mid = points_sorted_by_x[mid][0]
    left, right = points_sorted_by_x[:mid], points_sorted_by_x[mid:]

    pair_left, d_left = _closest_pair_rec(left)
    pair_right, d_right = _closest_pair_rec(right)
    best_pair, d = (pair_left, d_left) if d_left <= d_right else (pair_right, d_right)

    strip = [p for p in points_sorted_by_x if abs(p[0] - x_mid) < d]
    return _closest_in_strip(strip, d, best_pair)

def closest_pair(points):
    """Divide-and-conquer closest pair. O(n log^2 n) time (see article for the
    O(n log n) refinement that carries a y-sorted array through the recursion)."""
    if len(points) < 2:
        raise ValueError("closest_pair needs at least 2 points")
    px = sorted(points, key=lambda p: p[0])
    return _closest_pair_rec(px)

if __name__ == "__main__":
    points = [(2, 3), (3, 8), (5, 4), (7, 9), (8, 2),
              (9, 7), (11, 3), (12, 8), (13, 2), (15, 6)]
    pair, distance = closest_pair(points)
    print(f"Closest pair: {pair}, distance = {distance:.4f}")
    # Closest pair: ((13, 2), (11, 3)), distance = 2.2361

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <limits>
#include <stdexcept>
#include <vector>

struct Point { double x, y; };
struct Result { Point a, b; double dist; };

double distance(const Point& a, const Point& b) {
    double dx = a.x - b.x;
    double dy = a.y - b.y;
    return std::sqrt(dx * dx + dy * dy);
}

Result bruteForce(const std::vector<Point>& pts) {
    Result best{pts[0], pts[1], std::numeric_limits<double>::infinity()};
    for (std::size_t i = 0; i < pts.size(); ++i) {
        for (std::size_t j = i + 1; j < pts.size(); ++j) {
            double d = distance(pts[i], pts[j]);
            if (d < best.dist) {
                best = {pts[i], pts[j], d};
            }
        }
    }
    return best;
}

// Re-sorts the strip by y at every level: O(n log n) per level, O(n log^2 n) overall.
Result closestInStrip(std::vector<Point> strip, Result best) {
    std::sort(strip.begin(), strip.end(), [](const Point& p, const Point& q) { return p.y < q.y; });
    for (std::size_t i = 0; i < strip.size(); ++i) {
        for (std::size_t j = i + 1; j < strip.size() && (strip[j].y - strip[i].y) < best.dist; ++j) {
            double d = distance(strip[i], strip[j]);
            if (d < best.dist) {
                best = {strip[i], strip[j], d};
            }
        }
    }
    return best;
}

Result closestPairRec(const std::vector<Point>& byX) {
    std::size_t n = byX.size();
    if (n <= 3) {
        return bruteForce(byX);
    }
    std::size_t mid = n / 2;
    double xMid = byX[mid].x;
    std::vector<Point> left(byX.begin(), byX.begin() + mid);
    std::vector<Point> right(byX.begin() + mid, byX.end());

    Result bestLeft = closestPairRec(left);
    Result bestRight = closestPairRec(right);
    Result best = bestLeft.dist <= bestRight.dist ? bestLeft : bestRight;

    std::vector<Point> strip;
    for (const Point& p : byX) {
        if (std::abs(p.x - xMid) < best.dist) {
            strip.push_back(p);
        }
    }
    return closestInStrip(strip, best);
}

Result closestPair(std::vector<Point> points) {
    if (points.size() < 2) {
        throw std::invalid_argument("closestPair needs at least 2 points");
    }
    std::sort(points.begin(), points.end(), [](const Point& p, const Point& q) { return p.x < q.x; });
    return closestPairRec(points);
}

int main() {
    std::vector<Point> points = {
        {2, 3}, {3, 8}, {5, 4}, {7, 9}, {8, 2},
        {9, 7}, {11, 3}, {12, 8}, {13, 2}, {15, 6}
    };
    Result r = closestPair(points);
    std::printf("Closest pair: (%.0f, %.0f)-(%.0f, %.0f), distance = %.4f\n",
                r.a.x, r.a.y, r.b.x, r.b.y, r.dist);
    // Closest pair: (11, 3)-(13, 2), distance = 2.2361
}

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;

public class ClosestPairDivideAndConquer {
    record Point(double x, double y) {}
    record Result(Point a, Point b, double dist) {}

    static double distance(Point p, Point q) {
        double dx = p.x() - q.x();
        double dy = p.y() - q.y();
        return Math.sqrt(dx * dx + dy * dy);
    }

    static Result bruteForce(List<Point> points) {
        double bestDist = Double.POSITIVE_INFINITY;
        Point bestA = null, bestB = null;
        for (int i = 0; i < points.size(); i++) {
            for (int j = i + 1; j < points.size(); j++) {
                double d = distance(points.get(i), points.get(j));
                if (d < bestDist) {
                    bestDist = d;
                    bestA = points.get(i);
                    bestB = points.get(j);
                }
            }
        }
        return new Result(bestA, bestB, bestDist);
    }

    // Re-sorts the strip by y at every recursion level: O(n log n) per level,
    // O(n log^2 n) overall. See the article for the linear-merge refinement.
    static Result closestInStrip(List<Point> strip, Result best) {
        List<Point> byY = new ArrayList<>(strip);
        byY.sort(Comparator.comparingDouble(Point::y));
        double d = best.dist();
        Point bestA = best.a(), bestB = best.b();
        for (int i = 0; i < byY.size(); i++) {
            for (int j = i + 1; j < byY.size() && (byY.get(j).y() - byY.get(i).y()) < d; j++) {
                double dd = distance(byY.get(i), byY.get(j));
                if (dd < d) {
                    d = dd;
                    bestA = byY.get(i);
                    bestB = byY.get(j);
                }
            }
        }
        return new Result(bestA, bestB, d);
    }

    static Result closestPairRec(List<Point> pointsByX) {
        int n = pointsByX.size();
        if (n <= 3) {
            return bruteForce(pointsByX);
        }
        int mid = n / 2;
        double xMid = pointsByX.get(mid).x();
        List<Point> left = pointsByX.subList(0, mid);
        List<Point> right = pointsByX.subList(mid, n);

        Result resultLeft = closestPairRec(left);
        Result resultRight = closestPairRec(right);
        Result best = resultLeft.dist() <= resultRight.dist() ? resultLeft : resultRight;

        List<Point> strip = new ArrayList<>();
        for (Point p : pointsByX) {
            if (Math.abs(p.x() - xMid) < best.dist()) {
                strip.add(p);
            }
        }
        return closestInStrip(strip, best);
    }

    static Result closestPair(List<Point> points) {
        if (points.size() < 2) {
            throw new IllegalArgumentException("closestPair needs at least 2 points");
        }
        List<Point> byX = new ArrayList<>(points);
        byX.sort(Comparator.comparingDouble(Point::x));
        return closestPairRec(byX);
    }

    public static void main(String[] args) {
        List<Point> points = Arrays.asList(
            new Point(2, 3), new Point(3, 8), new Point(5, 4), new Point(7, 9), new Point(8, 2),
            new Point(9, 7), new Point(11, 3), new Point(12, 8), new Point(13, 2), new Point(15, 6)
        );
        Result r = closestPair(points);
        System.out.printf("Closest pair: %s-%s, distance = %.4f%n", r.a(), r.b(), r.dist());
        // Closest pair: Point[x=13.0, y=2.0]-Point[x=11.0, y=3.0], distance = 2.2361
    }
}

13. Testing and Edge Cases

Beyond the worked example, verify the implementation against these cases:

• Fewer than 2 points: the closest pair is undefined; both implementations above reject this input explicitly (raising/throwing) rather than returning a fabricated answer.
• All points identical: every pairwise distance is 0, so any pair is a correct answer at distance 0. Both the brute-force and divide-and-conquer versions handle this without special-casing, since a distance of exactly 0 still compares correctly with <.
• All points collinear: the strip and y-sort logic still work; with $y$ constant for every point, the "while $\Delta y < d$" loop simply scans further along the line, which is still bounded by the packing argument (collinear points fill cells no more densely than the general case in terms of the same-half separation guarantee).
• Ties for closest pair: when two or more pairs share the exact minimum distance, the algorithm returns whichever it encounters first (recursion order and scan order determine that); this is correct as long as the caller understands "a" closest pair is returned, not necessarily "the unique one" when ties exist.

These cases, the worked example, and 200 randomized point sets (sizes 2–60, integer coordinates in $[-50,50]$) were run through both the Python brute-force and Python divide-and-conquer implementations above; every trial produced matching distances. The Java implementations were compiled and executed directly against the worked example and matched the Python output exactly.

14. Applications and Alternatives

Alternatives exist at different scales and dimensions: for a fixed, static point set with many repeated nearest-neighbor queries, a k-d tree or a spatial grid amortizes preprocessing across many queries better than re-running this algorithm from scratch. For streaming or dynamic point sets where points are added and removed, sweep-line structures with balanced trees maintain an approximate or exact closest pair incrementally. This lesson's divide-and-conquer method is the right choice when you need one exact answer over a static batch of points and want a guaranteed $O(n\log n)$ (or $O(n\log^2 n)$ with the simpler strip re-sort) bound without extra data-structure machinery.

15. Exercises

Easy

1. Hand-trace (or code) the closest pair for the eight points $(1,1), (2,5), (3,2), (5,5), (6,1), (7,4), (8,2), (9,6)$. State the dividing line, both halves' winners, the strip, and the final answer.

Medium

1. Extend the algorithm to report every pair of points within a given threshold distance $r$ (not just the single closest pair). Describe how the strip step changes when more than one pair can qualify, and what happens to the "at most 7 neighbors" bound when $r$ is larger than the current best distance $d$.

Hard

1. Describe, without necessarily coding it, how this algorithm generalizes to points in 3D space. What replaces the "strip" (a 2D slab of points near the dividing plane)? Which coordinate do you sort the slab by? How does the packing argument change when cells become small cubes instead of small squares, and does the number of candidate neighbors per point stay a constant, or does it grow with dimension?

Review rhythm: tomorrow, re-derive the packing argument (8 points, 7 neighbors) from scratch on blank paper. Next week, re-implement the divide-and-conquer algorithm without looking at this page, then check it against the brute-force version on random inputs. Several weeks later, identify this same "sort, split, strip" shape the next time you meet a geometric divide-and-conquer problem, and try explaining the strip-and-packing argument to someone who knows recursion but has not seen this proof.

16. Summary Cheat Sheet

• Brute force checks all $\binom n2$ pairs in $\Theta(n^2)$; it is also the divide-and-conquer algorithm's own base case for small subproblems.
• Sort once by x, split at the median x into two halves, and recurse on each half.
• Let $d=\min(d_L,d_R)$; only points within $d$ of the dividing line (the "strip") can form a closer, cross-boundary pair.
• Sort the strip by y; each point needs comparison against at most the next 7 points in y-order — a packing/pigeonhole argument over a $d\times2d$ box split into eight $\frac d2\times\frac d2$ cells proves this bound.
• Recurrence $T(n)=2T(n/2)+O(n)$ solves to $O(n\log n)$; re-sorting the strip at every level instead of carrying a merged y-order costs an extra $\log n$ factor, giving $O(n\log^2 n)$ — still efficient and much simpler to implement correctly.
• Handle fewer-than-2-point input explicitly; identical points, collinear points, and tied closest pairs all fall out correctly without special-casing the core algorithm.