Closest Pair of Points Algorithm

问题:

I am currently working on implementing the closest pair of points algorithm in C++. That is, given a list of points (x, y) find the pair of points that has the smallest Euclidean distance. I have done research into this and my understanding of the algorithm is the following (please correct me if I'm wrong):

Split the array of points down the middle Recursively find the pair of points with the minimum distance for the left and right halves. Sort the left and right halves by y-coordinate, and compare each point on the left to its 6 closest neighbors (by y-coordinate) on the right. There is some theoretical stuff behind this, but this is my understanding of what needs to be done).

I've gotten the recursion part of the algorithm to work, but am struggling to find an efficient way to find the 6 closest neighbors on the right for each point on the left. In other words, given two sorted arrays, I need to find the 6 closest numbers in Array B for each point in array A. I assume something similar to merge sort is required here, but haven't been able to figure it out. Any help would be much appreciated.

回答1:

Sounds like you want a quad tree.

回答2:

Let dist = min(dist_L, dist_R) where dist_L, dist_R are the minimum distances found in the left and right sets, respectively.

Now to find the minimum distance where one point is on the left half and the other on the right half, you only need to consider points whose x-coordinates are in the interval [x_m - dist, x_m+dist].

The idea now is to consider the 6 closest points in this interval. So sort the points by y-coordinate for each point, look forward at the next 6. This will result in an O(nlog^2(n)) running time.

You can further improve upon this to O(nlogn) by speeding up the sorting process. To do this, have each recursive call also return a sorted list of the points. Then to sort the entire list, you just have to merge the two sorted lists. An observant reader would notice that this is precisely merge sort.