The problem is:

Suppose you're given $n$ points in the coordinate plane, and for convenience assume that no two of their $x$ or $y$ coordinates are the same. Design an algorithm that finds the shortest possible distance between a pair of these points. What is the time complexity of your algorithm?

Ofcourse there is a easy way to find the shortest distance in $\mathcal{O}(n^2)$. But, is there any better algorithm? I am out of idea.

Note: I am a Math major and not familiar with CS way to solve problems very much.


This is the well-known closest pair of points problem, and you can solve it for $n$ points in $O(n \log n)$ time by divide and conquer.

A pretty cool randomized algorithm due to Rabin is also available.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.