1. A method for estimating a vehicle deployment region, the method comprising the following operations performed by one or more processors: constructing a graph data structure using at least in part a single invocation of a form of Dijkstra's algorithm; partitioning an angular space centered on a vehicle location into a plurality of angular space regions, the vehicle location corresponding to a current or potential location of a vehicle; selecting, for at least three of the plurality of the partitioned angular space regions, a geographical location within the angular space region, wherein each selected geographical location in an angular space region is a geographical location furthest from the vehicle location, and wherein each selected geographical location was determined, using the graph data structure, to be reachable from the vehicle location within a specified maximum cost; and forming a polygon representing a vehicle deployment region from the selected geographical locations.