0

What kind of data structure should be used for nearest neighbor searching in 2d dimension?

I have searched and found out that there are many data structures for this: k-d tree, quadtree, octree. So what kind of structure should I use?

Vardan Hovhannisyan
  • 1,101
  • 3
  • 17
  • 40
  • 1
    Possible duplicates: http://stackoverflow.com/questions/3944649/suitable-choice-of-data-structure-and-algorithm-for-fast-k-nearest-neighbor-sear?rq=1 http://stackoverflow.com/questions/15820226/nearest-neighbor-search-in-2d-using-a-grid-partitioning?rq=1 http://stackoverflow.com/questions/4172358/all-k-nearest-neighbors-in-2d-c - did you research the existing answers? – eis Feb 07 '14 at 07:10
  • That depends on your requirements. Try a few and see what works best. – Henry Feb 07 '14 at 07:11

1 Answers1

1

I suggest a R-Tree, it's designed for that purpose.

pentadecagon
  • 4,717
  • 2
  • 18
  • 26
  • could you please clarify what kind of advantages its has over for example kd-tree. – Vardan Hovhannisyan Feb 07 '14 at 07:34
  • 1
    Frankly, I haven't used the latter so I can't tell in detail, but this question came up earlier: http://stackoverflow.com/questions/4326332/could-anyone-tell-me-whats-the-difference-between-kd-tree-and-r-tree – pentadecagon Feb 07 '14 at 07:47