LOCATION-BASED INFORMATION DETERMINATION

Techniques are described for determining and providing location-based information, including based on decomposing a geographic area into numerous smaller areas and using one or more layers of polygons to represent various of the smaller areas. In some situations, location-based information for a geographic area is determined efficiently and accurately to reflect actual travel distances and/or times, such as for use in identifying one or more points of interest that are sufficiently proximate to an indicated location (e.g., a current location of a user), and/or to determine actual travel distances and/or times between two or more indicated locations of interest. The location-based information determination may in some situations be performed in a realtime or near-realtime manner after a request is received from a user, such as to interactively provide results to the user that include or are based at least in part on the determined location-based information.