Search code examples
graphicsgeometrycomputer-sciencecomputational-geometrylocality-sensitive-hash

Nearest Neighbor Search

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

Solution

  • 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).