Previous [ 1] [ 2] [ 3] [ 4] [ 5] [ 6] [ 7] [ 8] [ 9] [ 10] [ 11] [ 12] [ 13] [ 14] [ 15] [ 16] [ 17] [ 18] [ 19] [ 20]

¡@

Journal of Information Science and Engineering, Vol. 30 No. 4, pp. 1445-1461 (September 2014)

Travel Time Distances Induced by Transportation Networks and General Underlying Distances*

SANG WON BAE1 AND KYUNG-YONG CHWA2
1Department of Computer Science
Kyonggi University
Suwon, 443-760 Korea
E-mail: swbae@kgu.ac.kr
2Department of Computer Science
Korea Advanced Institute of Science and Technology
Daejeon, 305-701 Korea
E-mail: kychwa@jupiter.kaist.ac.kr

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.

Keywords: computational geometry, shortest path, transportation network, travel time distance, Voronoi diagram

Retrieve PDF document (201409_09.pdf)

Received June 2, 2013; revised August 1, 2013; accepted September 5, 2013.
Communicated by Hee Kap Ahn.
* This research was supported by Kyonggi University Research Grant 2012. A preliminary version of this work was presented at the 16th ISAAC, Hainan, China, December 19-21, 2005.