Closest pair
- Algorithms course
- Expert
- Lesson 22/41
- 4 min
Find the closest pair with divide and conquer.
Closest pair
The closest pair problem aims to find the shortest distance between points in the plane. The naive method tries every pair and runs in O(n²).
The divide and conquer method splits points by x into two halves, recursively finds the closest pair in each half, then checks pairs crossing the boundary strip.
This method runs in O(n log n) time and O(n) space; significantly faster than the naive method.
Divide and conquer step
In divide and conquer we sort points by x and split them in half. We recursively find the closest pair in each half; let d be the minimum distance from the two halves.
Then we take a strip of width d around the middle line. We sort this strip by y and compare each point with the next few points.
The strip scan takes O(n) time; total complexity becomes O(n log n).
Practice closest_pair function
Write closest_pair(points). Return the squared distance of the closest pair in the point list (no square root). Print 2 with print(closest_pair([(0,0), (3,4), (1,1)])).
Starter code
def closest_pair(points):
# Squared distance of the closest pairSample solution
def closest_pair(points):
# Squared distance of the closest pair
n = len(points)
best = float('inf')
for i in range(n):
for j in range(i + 1, n):
dx = points[i][0] - points[j][0]
dy = points[i][1] - points[j][1]
d = dx * dx + dy * dy
if d < best:
best = d
return best
print(closest_pair([(0,0), (3,4), (1,1)]))Expected output
2
Questions and answers
Review the lesson questions together with their answers. To test yourself, solve the lesson interactively.
1 Complexity of the naive closest pair?
for i in range(n):
for j in range(i+1, n):- O(n)
- O(n log n)
- O(n²) Correct answer
- O(1)
Explanation: The nested loops run in O(n²).
2 distance computation
dx = points[i][0] - points[j][____]
dy = points[i][1] - points[j][1]dx = points[i][0] - points[j][0]
dy = points[i][1] - points[j][1]Explanation: The x component is at index 0.
3 Closest pair concepts
| Term | Meaning |
|---|---|
naive |
O(n²) |
divide and conquer |
O(n log n) |
squared distance |
No square root |
strip |
Middle region |