Voronoi diagrams with transportation on the euclidean plane

Abstract

With a transportation network, the distance is measured as the length of the shortest (time) path. This thesis investigates geometric and algorithmic properties of the Voronoi diagram with a transportation network on the Euclidean plane. In doing this, we introduce a needle, a generalized Voronoi site. We show that needles are suitable to interpret several proximity properties of the Euclidean plane equipped with a transportation network. We present an $O(nm^2 logn + m^3 logm)$ algorithm to compute the Voronoi diagram with a transportation network on the Euclidean plane, where n is the number of given sites and m is the complexity of the transportation network. And, if the speed on every road is equal and the given transportation network is isothetic, we can compute the diagram in $O(nmlogn + m^2 logm)$ time with maintaining the linear size of the diagram. Furthermore, a shortest path map with the transportation network can be constructed.