Closest Pair of Points
What you'll learn: How to find the two closest points in a 2D plane efficiently by dividing the space and carefully checking the boundary strip.
The Problem
Imagine you have a list of points scattered on a flat map, and you need to find which two are closest together. The naive approach—checking every pair—takes O(n²) time. We can do better using divide and conquer!
The Divide-and-Conquer Strategy
Divide: Sort points by x-coordinate and split them down the middle with a vertical line, creating left and right halves.
Conquer: Recursively find the closest pair in each half. Let's call the smaller distance d.
The Tricky Part – The Boundary Strip: The actual closest pair might have one point on the left and one on the right! So we must check points near the dividing line.
Here's the clever optimization: we only need to examine points within distance d of the middle line (the "strip"). Even better, for each point in the strip, we only need to check a few neighbors—at most 7 points ahead when sorted by y-coordinate. Why? Geometry proves that if two points are farther apart vertically than d, they can't be closer than d overall.
Why It Works
This approach runs in O(n log n) time—the initial sort costs O(n log n), and each level of recursion does O(n) work checking the strip. Much faster than the naive O(n²)!
Key Takeaway: The closest pair algorithm combines spatial division with a geometric insight—the strip search only needs to check a constant number of nearby points, making an O(n²) problem solvable in O(n log n) time.