# N Points on a Plane

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

Homework Helper
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

Staff Emeritus
Gold Member
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²)?

### Physics Forums Values

We Value Quality
• Topics based on mainstream science
• Proper English grammar and spelling
We Value Civility
• Positive and compassionate attitudes
• Patience while debating
We Value Productivity
• Disciplined to remain on-topic
• Recognition of own weaknesses
• Solo and co-op problem solving