Determining Closest City to Geoposition in O(1)

[ModShop]

For an assignment I have I need to parse a list of all the cities in the world, store it however I please and provide a method that can determine the closest city to a position given in latitude and longitude in (approximately) O(1). I've tried a number of various solutions but nothing I do seems to work.

The obvious solution is simply to loop all cities through and determine the closest city, but that's O(n). What I've tried is storing the cities in a structure vector<vector<vector<City> > > cities. The idea is that cities[i][j] would be a vector containing all cities whose latitude and longitude (after flooring) are i and j respectively. When a certain latitude and longitude is queried my method floors it and begins searching in the cities structure from the floored location and expands the search radius outwards until it finds cities, and then it grabs the closest of that subset of cities. Due to the non-linear nature of latitude and longitude, however, the actual method isn't quite as elegant.

Does anyone have any other ideas of how I could possibly approach the problem? I don't need code, just conceptual ideas. Thanks!

[ne555]

> and expands the search radius outwards until it finds cities
¿How do you do that expansion?
I think that the biggest problem is that you may end with big regions of empty cells. It would be better if you make sure that each cell has at least one city,

I'll suggest you to look at quadtrees or range trees.
Haven't thought on how to adapt them to an spherical surface.

[ModShop]

I iterate over the elements in the vectors contained in the range ([-i,i],[-i,i]), increasing i until a city is found. After a city is found I continue increasing i a few more iterations due to the nonlinear nature of latitude and longitude. There are plenty of empty cells but I'm not really sure how to circumvent that. I want to use vectors because of the constant random access time.

I looked up quad trees, they seem really promising. I'll have to figure out how to implement them.

[htirwin]

Quad tree will give you O(logn).

Just add another level of indirection.

[ModShop]

@htirwin: What do you mean by "another level of indirection"?

I think a problem with my solution is that it searches a square region rather than circular. It may find the first city in one of the corners of the square and stop searching, even though a closer city may exist just outside of the box. To account for this I continue to expand the size of the box for a while after the first city is found, which I think it what is hurting my efficiency.

[helios]

This has a best case of O(1) but a worst case of O(n), depending on the relative distribution of the cities:

Initialization phase:
1. Partition the Earth into bins. The size and shape don't matter, but the bin should be easily computed from the input coordinates.
2. Compute the Voronoi cells for all the cities.
3. Every bin should be associated with every cell it overlaps with.

Lookup phase:
1. Determine the bin that contains the input.
2. If the bin associated with a single cell, that city is the closest to the input.
3. Otherwise all the cities that are associated with the bin need to be checked.

[ModShop]

@helios: That's beautiful! I came up with a similar concept to Voronoi cells, but I had no idea how to implement it, let alone that it was already a thing. I'll definitely give your algorithm a shot if my solution doesn't pan out.