Shortest distance between points algorithm

Question

Given a set of points on a plane, find the shortest line segment formed by any two of these points.

How can I do that? The trivial way is obviously to calculate each distance, but I need another algorithm to compare.

Answer 1

http://en.wikipedia.org/wiki/Closest_pair_of_points

The problem can be solved in O(n log n) time using the recursive divide and conquer approach, e.g., as follows:

• Sort points along the x-coordinate
• Split the set of points into two equal-sized subsets by a vertical line x = xmid
• Solve the problem recursively in the left and right subsets. This will give the left-side and right-side minimal distances dLmin and dRmin respectively.
• Find the minimal distance dLRmin among the pair of points in which one point lies on the left of the dividing vertical and the second point lies to the right.
• The final answer is the minimum among dLmin, dRmin, and dLRmin.

Answer 2

I can't immediately think of a quicker alternative than the brute force technique (although there must be plenty) but whatever algorithm you choose don't calculate the distance between each point. If you need to compare distances just compare the squares of the distances to avoid the expensive and entirely redundant square root.