Nearest Neighbor Search

Question

I want an algorithm for Nearest Neighbor Search(NNS) Problem. The problem is related to Computational Geometry field. I searched a lot, but i did not find an algorithm for that. I think locality sensitive hash(LSH) algorithm will be good for this problem, but unfortunately i didn't find an algorithm for this. Exactly i want an article to learn LSH. Can any one help me?

Thanks

Answer 1

IMHO LSH are quite hard to implement correctly.

Great articles about NNS is at wiki. I'm using kd-tree for NNS for solving nearest neighbor problem when merge two triangle meshes together and it works quite well and pretty fast. It's also not that hard to implement (some implementations might be found by google easily).

Answer 2

If you are looking for a C++ library, you can have a look at this CGAL package. There is also the ANN library.

Answer 3

Do you need nearest neighbour or approximate nearest neighbour? In how many dimensions?

I would also recommend trying kd-tree search before LSH.