Computing driving directions has motivated many shortest path heuristics that answer queries on continental scale networks, with tens of millions of intersections, literally instantly, and with very low storage overhead. In this paper we complement the experimental evidence with the first rigorous proofs of effciency for many of the heuristics suggested over the past decade. We introduce the notion of highway dimension and show how low highway dimension gives a united explanation for several seemingly different algorithms.

PDF file

In  Proc. ACM-SIAM Symposium on Discrete Algorithms (SODA10)

Publisher  Society for Industrial and Applied Mathematics
Copyright © 2010 by Society for Industrial and Applied Mathematics.

Details