Closest pair of points problem

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(n2) time, finding the smallest distance between all nC2 = 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:

  1. Sort points according to x-coordinate.
  2. Recursively find the closest pairs in the left and right halves. Let ‘d’ be the smallest distance found so far.
  3. Find all the points whose x-coordinate is closer to the middle line (assume a vertical line passing through the middle point) than d.
  4. 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.
  5. 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

3 thoughts on “Closest pair of points problem

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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s