Solving Riddle: Find Closest 2 Points on a Plane in O(N)

[Atlas]

Here's a riddle I'm having trouble solving:
There are N points on a plane. Find the two points that are closest, in time better than O(N^2).

Any idea?
Thanks :)

 

[ComputerGeek]

randomly pick point p. then choose point P+1...

 

[AKG]

Nice problem. Are you sure there is a solution? I'll think on it some more if you know that it can be solved (well, I'll think on it anyways).

 

[Atlas]

I know there's a so-called "simple" solution that requires O(N * log^2(N)), and a more complex one that requires O(N * log(N)).

 

[Hurkyl]

Here's a hint:

If the problem was "Given an arbitrary function f(P, Q) of two points, find the pair of points that minimizes f(P, Q)", can you prove that the best algorithm is Θ(n²)?

 

[Atlas]

Found a solution here:
http://www.cs.mcgill.ca/~cs251/ClosestPair/ClosestPairDQ.html