Travel Time Distances Induced by Transportation Networks and General Underlying Distances

Abstract

This paper considers a generalization of travel time distances by taking general underlying distance functions into account. We suggest a reasonable set of axioms defining a certain class of distance functions that can be facilitated with transportation networks. It turns out to be able to build an abstract framework for computing shortest path maps and Voronoi diagrams with respect to the induced travel time distance under such a general setting. We apply our framework in convex distance functions as a concrete example, resulting in efficient algorithms that compute the travel-time Voronoi diagram for a set of given sites. More specifically, the Voronoi diagram with respect to the travel-time distance induced by a convex distance based on a k-gon can be computed in O(m(n + m)(k log(n + m) + m)) time and O(km(n + m)) space, where n is the number of Voronoi sites and m is the complexity of the given transportation network.