If I want to make N repeated (i.e. millions of) 2D nearest-neighbor queries on a pointset of size M, is traveling down into a KD-Tree most efficient or are there better ways to do this? (e.g. Voronoi?)

Right now I'm building a KD-Tree of size M, so with N queries on that I end up using N log M time. Can I do better?

  • $\begingroup$ Related: space partitioning DS. I'd also check out Foundations of Multidimensional and Metric Data Structures, probably don't read the entire book unless you're truly interested, but you can see the table of contents on amazon and maybe get some ideas from there. $\endgroup$ – ryan Oct 20 '17 at 13:26
  • $\begingroup$ What do you mean by better? Can you tell anything about the data? Are queries bounded somehow? If you could switch to Octrees, you may save a lot in terms of performance, but lose a bit with memory. With proper indexing it may be a hash table with octree at the bottom. $\endgroup$ – Evil Oct 20 '17 at 15:53
  • $\begingroup$ If $N = \Omega(M^2)$, then you can just build a huge lookup table in $O(M^2)$ time and space that contains the answer for every possible query, and then answer each query in $O(1)$ time. A second idea: Is it necessary to answer each query before the next one arrives? If not, it might be possible to get practical (and possibly even theoretical) speedups by answering them in a different order. $\endgroup$ – j_random_hacker Oct 21 '17 at 15:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.