Navigation systems assist almost any kind of motion in the physical
world including sailing, flying, hiking, driving and cycling. On the other hand,
traces supplied by global positioning systems (GPS) can track actual time and
absolute coordinates of the moving objects.
Consequently, this paper addresses efficient algorithms and data structures for
the route planning problem based on GPS data; given a set of traces and a current
location, infer a short(est) path to the destination.
The algorithm of Bentley and Ottmann is shown to transform geometric GPS
information directly into a combinatorial weighted and directed graph structure,
which in turn can be queried by applying classical and refined graph traversal
algorithms like Dijkstras' single-source shortest path algorithm or A*.
For high-precision map inference especially in car navigation, algorithms for road
segmentation, map matching and lane clustering are presented.