Monday, February 25, 2013

Closest Pair Algorithm

Say you are given a set of points in the plane and you want to find the two points closest to one another. The brute force method of doing this would be to compute the distance between every possible pair of points and keep track of the minimum. This will take O(n2) because there is a quadratic number of pairs.

Let's assume that this problem were on a line, or 1-D. Then we can just sort all the points, O(nlogn) at best, and then run through the line to find the closest pair which must be adjacent points, O(n). So can we find a similar method that will solve the problem in 2-D?

We can sort the points according to x-coordinate and y-coordinate which will just take O(nlogn). This may not work for all points. If we wish to apply the divide and conquer method to solving this problem,  we might think to split the problem in half, recursively do work in each half, and combine the solutions of the subproblems to recover the solution to original problem.

We can let Q be the left half of P and R be the right half of P, which forms Qx, Qy, Rx, and Ry.

No comments:

Post a Comment