Fastest way to find minimum distance between points

Question

I have a set of 2D points and need to find the fastest way to figure out which pair of points has the shortest distance in the set.

What is the optimal way to do this? My approach is to sort them with quicksort and then calculate the distances. This would be O(nlogn + n) = O(nlogn).

Is it possible to do it in linear time?

Thanks.

Answer 1

No. Minimum distance among ALL points in O( n ^ 2 ) because you must compare every point against every other point. Technically it's n * n / 2 because you only have to fill have to fill half the matrix.

There are faster algorithms are for finding the nearest neighbor to a given point. Unfortunately, you have to then do this for every point to find the closest two points.

Answer 2

it is actually http://en.wikipedia.org/wiki/Closest_pair_problem

Answer 3

If you could probe out a constant amount from each point and use iterative deepening DFS, youd never check further apart than the two closest points...and since you're not dependent on a failed pass, you'd never need to recompute the way ID DFS tends to.