Warp wrote:
> 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).

I don't think you could start with an unsorted flat array and get better 
than O(n) time. It would have to take that long to build the 
PR-quadtree. But yah, if you know you're going to need this...

>   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.

Yep. That's what I came up with.

-- 
Darren New / San Diego, CA, USA (PST)
  Helpful housekeeping hints:
   Check your feather pillows for holes
    before putting them in the washing machine.

Post a reply to this message