What algorithm would be most efficient when trying to find the nearest city given a set of coordinates?
This answer is very similar to that of ckc.
First, spilt the 1000 cities in 2 groups : a big one located located between Canada and Mexico and the few others cities located outside this rectangle (i.e Alaska, Hawai, ...).
When processing coordinates, check if they belong to the small group : in this case, no optimisation needed.
To optimize the other case, you may divide the map in rectangles (example 5°lat x 7° lon) and associate to each rectangle the list of cities belonging to each rectangle.
To find the nearest city, consider the rectangle R containing the point.
Compute the distance to the cities of the rectangle.
Process the 8 rectangles adjacent to R by computing the distance of the point to each rectangle : you may then eliminate the adjacent rectangles whose distance is greater than the best distance already found.
Iterate the process to a next level, i.e. the next crown (rectangles located on the outside of the area composed of 5x5 rectangles whose center is R).
I have a dataset which contains the longitude and latitude of the 1000 largest US cities. I'm designing an API which returns the user's nearest city, given an input of the user's longitude/latitude.
What is the most efficient algorithm I can use to calculate the nearest city? I know that I can use the haversine formula to calculate the distance between the user's coordinate and each cities, but it seems inefficient to have to do this for all 1000 cities. I've previously used a k-d tree to solve nearest neighbour problems on a plane - is there a similar solution that can be used in the context of a globe?
Edit: keeping this simple - distance I'm looking for is as the crow flies. Not taking roads or routes into account at this stage.