1. One-Liner
Given 2D points, find the minimum distance between any two using divide-and-conquer on the x-sorted order plus a strip merge in y-order.
2. The Problem It Solves
Brute force is O(n²); the classic D&C algorithm achieves O(n log n) for Euclidean closest pair—foundational in computational geometry and collision detection prep.
3. The Core Idea
Split by a vertical line; closest pair is either both left, both right, or one on each side within distance δ of the line—only O(n) strip candidates need pairwise checks (constant neighbors in y-order).
4. How It Works (Step-by-Step)
| Step | What Happens | ||
|---|---|---|---|
| 1. Sort | Sort points by x (and maintain y-sorted lists or merge). | ||
| 2. Base | If n ≤ 3, brute-force min distance. | ||
| 3. Divide | Split at median x; recurse for δ = min(δ_L, δ_R). | ||
| 4. Combine | Build strip where | x − midx | < δ; scan y-order, compare to next ≤7 points. |
5. Dry Run Example
Four corners of a unit square: brute base finds 1 edge length; after split, strip checks cross-pairs near the middle vertical.
6. Key Properties
| Property | Value |
|---|---|
| Time | O(n log n) with careful merging |
| Space | O(n) for auxiliary arrays |
| Metric | Euclidean (typical); extensions vary |
7. Where It Is Used
| Domain | Use |
|---|---|
| Graphics / GIS | Nearest neighbor preprocessing |
| Robotics | Collision checks, clustering |
8. Interview Tips
Explain why strip is narrow and 7-point constant in y-order; state handling duplicates and integer vs float precision.
9. Comparison with Other Algorithms
| Method | Time | Notes |
|---|---|---|
| Brute force | O(n²) | Simple |
| D&C closest pair | O(n log n) | Standard plane algorithm |
| KD-tree | Build + query | Different structure |
10. Complexity
| Metric | Value |
|---|---|
| Time | O(n log n) |
| Space | O(n) |
Implementation Example (PYTHON)
import math
def dist(p, q):
return math.hypot(p[0] - q[0], p[1] - q[1])
def closest_pair(px):
n = len(px)
if n <= 3:
return min((dist(px[i], px[j]) for i in range(n) for j in range(i + 1, n)), default=float('inf'))
mid = n // 2
xmid = px[mid][0]
dl = closest_pair(px[:mid])
dr = closest_pair(px[mid:])
d = min(dl, dr)
strip = [p for p in px if abs(p[0] - xmid) < d]
strip.sort(key=lambda p: p[1])
for i in range(len(strip)):
for j in range(i + 1, min(i + 8, len(strip))):
d = min(d, dist(strip[i], strip[j]))
return d