Farthest voronoi diagrams for a transportation network on the euclidean plane

Abstract

With a transportation network, the distance is measured as the length of the shortest (time) path. Algorithms for computing nearest Voronoi diagrams with a transportation network were proposed by Palop and Bae, respectively. But, algorithms for computing farthest Voronoi diagrams for a transportation network is not known. In this thesis, we consider the farthest Voronoi diagram problem for a transportation network on the Euclidean plane. We show that this problem is reduced to farthest color Voronoi diagram problem and present an $O(nm^3 + n^2m^2α(n^2m^2) log nm)$ algorithm to compute. And, we also show that the diagram can have bounded faces and disconnected faces. However, we prove the structural complexity of the diagram is $O(nm^2)$ which predicts the existence of a better algorithm.