There are a number of very good geo reference techniques simpler then R-tree, S2 etc, that may limit the number of polygons they have to check even further, mos

There are a number of very good geo reference techniques simpler then R-tree, S2 etc, that may limit the number of polygons they have to check even further, mostly depending on their polygon definition. For example, indexing the polygons by latitude deg and longitude deg, e.g. 38.118 stored as a decimal with the values being each of the polygons that sit within that degree block. You can get more fine grained by increasing the number of total degree digits you store for both latitude and longitude as well (3805.11825). This requires very little processing power and is fairly simple to update affecting generally fairly small regions and datasets. Now instead of searching even hundreds of polygons you are probably searching 10's, and you could cut it down further. My bet is that with this technique you could get it down to say 10 or less polygons to check. Of course, a lot depends on their polygon definitions. But the other advantage is that this technique works globally, regardless of country, state or territory and without having to worry about how to define "city". It essentially should save 1 of the O(n) lookups to find the right city, given city names are not always unique even within a state (Germany, Canada, U.S., Mexico etc all have this issue). Maybe I am missing something though, I can't imagine they didn't go through this type of exercise. I would be curious, if this or some of the other common indexing techniques were considered though and why this one or others were ruled out? Also are they truly indexing every small city or more like MSA's?