1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

N Points on a Plane

  1. Aug 26, 2005 #1
    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 :)
  2. jcsd
  3. Aug 26, 2005 #2
    randomly pick point p. then choose point P+1.... :-p
  4. Aug 26, 2005 #3


    User Avatar
    Science Advisor
    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).
  5. Aug 26, 2005 #4
    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)).
  6. Aug 26, 2005 #5


    User Avatar
    Staff Emeritus
    Science Advisor
    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²)?
  7. Aug 27, 2005 #6
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook