Closest Pair of Points

Finds the two closest of n points in the plane in O(n log n), beating the O(n²) brute-force check of every pair. Split by x-coordinate, solve each half recursively, then check only a thin boundary strip for a closer cross pair.

Category: Divide and Conquer
Time complexity: O(n log n)
Space complexity: O(n)

Pseudocode

sort points by x, split at the median
recursively find closest pair in each half
d ← min(left, right)
check the strip within d of the split line, sorted by y

Reference implementation

def closest(pts):
    if len(pts) &lt;= 3: return brute_force(pts)
    mid = len(pts) // 2
    dl = closest(pts[:mid]); dr = closest(pts[mid:])
    d = min(dl, dr)
    strip = [p for p in pts if abs(p.x - pts[mid].x) &lt; d]
    return min(d, strip_closest(strip))

Open the interactive Closest Pair of Points visualisation →