Reverse Geocoding Without Web Access

I am working on an application where one of the requirements is that I be able to perform realtime reverse geocoding operations based on GPS data. In particular, I must be able to determine the state/province to which a latitude, longitude pair maps and detect when we have moved from one state/province to another.

I have a couple ideas so far but wondered if anyone had any ideas on either of the following:

• What is the best approach for tackling this problem in an efficient manner?
• Where is a good place to find and what is the appropriate format for North American state/province boundaries

As a starter, here are the two main ideas I have:

1. Break North America into a grid with each rectangle in the grid mapping to a particular state province. Do a lookup on this table (which grows quickly the more precise you would like to be) based on the latitude and then the longitude (or vice versa).
2. Define polygons for each of the states and do some sort of calculation to determine in which polygon a lat/lon pair lies. I am not sure exactly how to go about this. HTML image maps come to mind as one way of defining the bounds for a state/province.

I am working in python for the interested or those that might have a nice library they would like to suggest.

To be clear... I do not have web access available to me, so using an existing reverse geocoding service is not an option at runtime

I suggest using a variant of your first idea: Use a spatial index. A spatial index is a data structure built from rectangles, mapping lat/long to the payload. In this case you will probably map rectangles to state-province pairs. An R-tree may be a good option. Here's an R-tree python package. You could detect roaming by comparing the results of consecutive searches.