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?
Best Answer
This is easy.
Remember