Closest pair

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).

Exercise 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)])).

Show example 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)]))

Test yourself

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²)
- O(1)
Show answer

O(n²) — The nested loops run in O(n²).

distance computation

dx = points[i][0] - points[j][____]
dy = points[i][1] - points[j][1]

Show answer

dx = points[i][0] - points[j][0]
dy = points[i][1] - points[j][1]

Closest pair concepts

naive

O(n²)
divide and conquer

O(n log n)
squared distance

No square root
strip

Middle region

Next lesson: Point in polygon

We Are Enhancing Your Experience

Cookie Preferences

Strictly Necessary Cookies

Analytical Cookies