Geometric Travel Planning

static in the sense that it is not possible to update them due to the
construction of a new route or street. Also, it is not possible to query
them for a route that is to be traveled at a particular point of time.

We review a novel approach that allows the construction of maps from
Global Positioning System (GPS) trajectories and efficient computational
geometry algorithms. Given a set of GPS points, the input is refined
by geometric filtering and rounding algorithms. For constructing the graph
from these GPS points and the according point-localization structure, fast
scan-line and divide-and-conquer algorithms are used.

For accelerating the search algorithms, the geometrical structure of the
graph is exploited in two ways. The graph is compressed while retaining
the original information for unfolding resulting shortest paths. It is
then annotated by refined topographic information: e.g., by the bounding
boxes of all shortest paths that start with a given edge.

The sudden changes in the road network: e.g., a road accident or traffic
jam can affect the topology of the graph by increasing the travel time
along that edge. This in turn can affect the pre-computed information. We
review some of the approaches to efficiently characterize the invalid
pre-computed information.