What's a good algorithm for nearest neighbour problem in two dimensions?

Question

I would like to build an app that's going to give you the closest restaurant depending on your location. We'll have a database with all the POI corresponding to the restaurant and we'll get your location with the GPS of your phone...

What algorithm would be appropriate ? Where can I find good doc about it ?

Thanks

Answer 1

Here's an informative presentation: http://dimacs.rutgers.edu/Workshops/MiningTutorial/pindyk-slides.ppt

I would either use a Quadtree or a Kd-tree.

See some benchmarks here: http://www.flegg.net/brett/pubs/spatial/index.html. It really all depends on your data size and range.

Answer 2

The main problem is how do you store and search the data. If you are using a SQL database that doesn't support spatial indexes (let's say SQLite on Android), consider converting the spatial data to a linear Z-order curve. The algorithm is simple, I know about (well, wrote) this implementation.