N Points on a Plane

  • Thread starter Atlas
  • Start date
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 :)
 
randomly pick point p. then choose point P+1.... :-p
 

AKG

Science Advisor
Homework Helper
2,559
3
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).
 
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
Science Advisor
Gold Member
14,847
17
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²)?
 

Related Threads for: N Points on a Plane

  • Posted
Replies
21
Views
4K
Replies
1
Views
2K
  • Posted
Replies
4
Views
2K
Replies
3
Views
1K
  • Posted
Replies
13
Views
2K

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

Hot Threads

Top