Nearest Pair: Find the Closest Pair of Points in 2D Space

Question

## Problem

Given N points in 2D space, find the pair with the minimum Euclidean distance.

```python
from typing import List, Tuple

def closest_pair(points: List[Tuple[float, float]]) -> Tuple[Tuple[float,float], Tuple[float,float], float]:
    # returns: (point_a, point_b, distance)
    pass
```

**Example:**
```
points = [(0,0),(3,4),(1,1),(5,2)]
closest_pair(points)
-> ((0,0), (1,1), 1.4142...)
```

A brute-force O(n^2) solution is expected first. Then discuss the divide-and-conquer approach.

## Approach

Divide-and-conquer: sort by x, split at median, recurse on each half, then check the strip of width 2*delta around the midline. The strip check is O(n) because each point in the strip can have at most 7 neighbors within delta.

## Follow-ups

1. Walk through the strip check. Why is the constant 7 (or 8) the bound on neighbors?
2. What is the recurrence and resulting complexity of the divide-and-conquer algorithm?
3. How does this generalize to k-dimensional space?
4. When would a k-d tree outperform divide-and-conquer for this problem?

Nearest Pair: Find the Closest Pair of Points in 2D Space

Question Details

Full Details

Topics

More from Waymo