The closest pair problem is a problem in computational geometry where the objective is to find a pair of points having the minimum euclidean distance between them.

**Input:** N points in Euclidean space

**Output:** A pair of points having the smallest Euclidean distance between them

Brute force algorithm for this problem takes O(n^{2}) time, finding the smallest distance between all ^{n}C_{2} = n(n-1)/2 pairs of points and can be described as follows:

However, the closest pair problem can be solved in O(nlogn) using a divide and conquer approach as follows:

- Sort points according to x-coordinate.
- Recursively find the closest pairs in the left and right halves. Let ‘d’ be the smallest distance found so far.
- Find all the points whose x-coordinate is closer to the middle line (assume a vertical line passing through the middle point) than d.
- Find the closest pair among the points found in the previous step. It can be proven geometrically that each point needs to be compared to only the next 7 points in the worst case so this step takes only linear time.
- Return the closest pair from the pairs found in steps 2 and 4.

Take a look at the C++ implementation.

Try your hand at problem CLOPPAIR, which uses this idea.

**Reference:** Algorithms 4th Edition by Robert Sedgewick and Kevin Wayne

Advertisements

Find all the points having a distance less than ādā from the middle point. There can be at most 8 such points.

In this what do you mean by middle point? Is it the median of the sorted array?

Would you please elaborate as to why only 8 such points can be there?

I’ve updated the post to correct the algorithm description.

The middle point is A[n/2] in the array A sorted by x coordinates, assuming the array had n points. When n is even, we can use any of the two middle points.

d is the minimum distance found in the left half and the right half. But there may be some points such that one point lies in the left half and the other in right, whose distance is less than d so d is effectively an upper bound on the minimum distance.

We find all points in the array whose x-coordinate lies closer to the middle line than d. It can be proven geometrically that we only need to compare among subsets of at most 8 points, i.e., 1 point needs to be compared to at most 7 points after it in sorted order by y-coordinate to find the closest pair.

The proof works like this:

Imagine a square of side 2d with center at the middle point. Since d is the minimum distance found in the left and right halves, at most 8 points can lie in this square, while simultaneously maintaining the constraint that points in left half must be separated by at least d distance from other points in the left half, similarly for points in right half.

The worst case occurs when 4 points lie on the 4 corners and 4 on the centers of 4 sides of this square.

Look at this for a detailed proof: http://people.csail.mit.edu/indyk/6.838-old/handouts/lec17.pdf