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

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 开发者_JAVA百科your phone...

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

Thanks

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.

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.