What algorithm would be most efficient when trying to find the nearest city given a set of coordinates?
You can split the map into squares that do not overlap and they cover the whole US map (i.e., you will have a grid). You will number the squares using the coordinates of their upper left corner (i.e., each one will have a unique ID) and you will do a preprocessing where each city will be assigned with the ID of the square where it belongs. You will find the square where the user lies into and then you will check only the cities that lie into this square and the ones that are one step from this (total: 9 squares). If these are empty of cities, you will check the ones that are two steps of it etc. In this way, on average you will check much less cities to find the closest
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.