Darren New <dne### [at] sanrrcom> wrote:
> Given a large number N of points (say, millions) in a 2D cartesian 
> space, how do you find the K points closest to the origin most 
> efficiently?  E.g., you have a million (X,Y) pairs in an unsorted array; 
> how do you find the five thousand pairs with the smallest (X*X+Y*Y) values?

  If you are allowed to post-process, a PR-quadtree can be used to find
points closest to another point quite fast (faster than O(n), iirc).

  If you are not allowed to post-process, then I can't think of anything
else than using http://en.wikipedia.org/wiki/Selection_algorithm and then
searching for all points smaller than the found one, which would be linear
complexity in average.

  (That page, in fact, describes finding the n smallest elements, and
comments: "The resulting algorithm requires an expected time of only O(n),
which is just about the best any algorithm can hope for.")

-- 
                                                          - Warp

Post a reply to this message