Is there any better way to find the closest points' distance?

Question

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.

Answer 1

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.