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

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..