Algorithmic solution to find closest city based on lat/lon

Question

Note there are other similar questions but 1) I don't want to rely on an online service, 2) I'm looking for a clean algorithmic solution.

I have a database of cities and their latitudes/longitudes. I'm looking for a way that, given an arbitrary lat/lon, finds the closest city.

Solutions I can think of so far:

1. The obvious brute force solution is, of course, to calculate all the possible distances using the great-circle distance formula. This also takes a long time and is O(n).

2. A modification of the KD-Tree algorithm may work, but I'm at a loss as to how to modify this algorithm to work in non-cartesian coordinates, as is the case for lat/lon. We can assume Mercator projection if this helps.

3. Use a geo-database such as PostgreSQL. This doesn't work for me, period.

Any insights?

Answer 1

You could think of it as a 3D problem. Convert (lat, lon) coordinates to (x, y, z) coordinates. This only needs to be done once for your database.

For each test point, convert to (x, y, z) and compute the squares of the chord distances (for speed and simplicity) to each city. Choose the closest one. I believe the closest city in 3-space will also be the closest city in terms of the great circle distance.

If you need the great circle distance, you can compute it for just the closest city.

With (x, y, z)-space, there's probably a spatial partitioning structure you can use to limit which cities you actually have to check. I don't think there's one that will help directly in (lat, lon)-space. But O(N) really isn't that bad. Also, the problem vectorizes pretty well.

Answer 2

I think you cannot save on computing the distance matrix between the cities, just use the Haversine formula formula for it. Computing the matrix is to be done only once, and you can use it later every time you need it without any complicated cast.

You might compute distance with MySQL also if you have no access to PostgreSQL, e.g. see this article on Google Code for details. The part, dealing with your problem could be summarized in the following SQL query:

SELECT id, ( 3959 * acos( cos( radians(37) ) * cos( radians( lat ) ) * cos( radians( lng ) - radians(-122) ) + sin( radians(37) ) * sin( radians( lat ) ) ) ) AS distance FROM cities ORDER BY distance LIMIT 1;