# Finding the closest n points to any arbitrary point in two dimensions (r-tree, quadtree, spatial index)

I have a distribution of two dimensional point objects. How is it possible to find the nearest N number of points to any given point without iterating over the entire collection of points (and only keeping the smallest 'n')? I will be doing this for every point so brute force technique (which i'm using right now. There are 12,000+ points within this set so sometimes premature optimization is the.. mature route to take.

I've looked at R-trees however as far as i'm aware they return all points within a given distance of a point, this could potentially work but i'd need to start at an extremely small distance and make successively larger searches until 'n' are found. Perhaps i'd even need to create a custom geometric circle object and use this to bound the search instead of the default square, thoughts on this approach? Is the circle necessary?

Are quadtrees any better for this? Is it possible to traverse from smallest to largest boxes in search of 5 closest points? It seems this might have potential too -- although i've only taken a cursory glance at this algorithm compared to r-trees.

What's the best way to tackle this accurately without resorting to brute force?

• Apr 14, 2015 at 14:03
• What exactly is your question? It sounds like you have identified 2 good candidate algorithms, and you need to research more and decide between them. Apr 14, 2015 at 14:04
• @MobyDisk - OP is looking for a comparison between the two algorithms and has provided a measure of scale to help evaluate the two algorithms. It seems on-topic enough to me.
– user53019
Apr 14, 2015 at 14:13
• Regarding taking small steps: Don't overly worry about getting too many points. Extra points is often not that bad: if you wanted 5 but got 50, that's okay. Just sort the 50 points by distance. That is a lot less than sorting 12,000 points by distance. If your iterations are too small you will just waste CPU time. It is similar to having a quadtree where you work really hard to have each quad have only 1 point. You will spend more time subdividing than it is worth. Apr 14, 2015 at 14:20
• @MobyDisk thank you. Even writing out the above in plain english instead of crunching information in my brain helped me further understand what I am and am not looking for. You're right about not incrementing too small. Any suggestion in the relative size I should scale compared to the total space (a uniform distribution could be assumed I suppose)? If not I can just run a series of tests on my actual data to find a good size of increase. Apr 14, 2015 at 14:49