Fastest way to find minimum distance between point

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:

The closest pair of points problem or closest pair problem is a problem of computational geometry: given n points in metric space, find a pair of points with the smallest distance between them...

In the computational model which assumes that the floor function is computable in constant time the problem can be solved in O(n log log n) time. If we allow randomization to be used together with the floor function, the problem can be solved in O(n) time..

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.