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

¡@

SANG WON BAE^{1} AND KYUNG-YONG CHWA^{2}

*
^{1}Department of Computer Science
Kyonggi University
Suwon, 443-760 Korea
E-mail: swbae@kgu.ac.kr
^{2}Department 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.