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