N Points on a Plane

  • Thread starter Atlas
  • Start date
  • #1
5
0
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 :)
 

Answers and Replies

  • #2
379
0
randomly pick point p. then choose point P+1.... :-p
 
  • #3
AKG
Science Advisor
Homework Helper
2,565
4
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).
 
  • #4
5
0
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)).
 
  • #5
Hurkyl
Staff Emeritus
Science Advisor
Gold Member
14,916
19
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 on N Points on a Plane

  • Last Post
Replies
21
Views
4K
  • Last Post
Replies
5
Views
3K
  • Last Post
Replies
7
Views
3K
Replies
3
Views
5K
Replies
4
Views
553
  • Last Post
Replies
4
Views
2K
  • Last Post
Replies
5
Views
2K
  • Last Post
Replies
3
Views
2K
  • Last Post
Replies
2
Views
1K
Top