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[3] and Bae[6], 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\alpha(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.
트랜스포테이션 모델에서는 두 점사이의 거리를 한 점에서 다른 점으로 가는데 걸리는 최소의 시간으로 측정한다. 이러한 모델에서의 보로노이 다이어그램 문제는 Palop[3]과 Bae[3]이 제시하고 해결한 바 있다. 하지만 트랜스포테이션 모델에서 최장 보로노이 다이어그램 문제에 대한 해법은 아직 알려진 바가 없다.
이 논문에서는 트랜스포테이션 네트워크에서의 최장 보로노이 다이어그램 문제에 대한 해법을 제시한다. 우리는 이 문제가 최장 색깔 보로노이 다이어그램 문제라는 것을 보이고 이를 이용해 $O(nm^3+n^2m^2\alpha(n^2m^2)lognm)$ 시간복잡도를 가지는 계산 알고리즘을 제시한다. 그리고 이 최장 보로노이 다이어그램이 기존의 유클리디언 모델에서의 최장 보로노이 다이어그램과는 다르게 한정된 영역과 끊긴 영역을 가질 수 있다는 것을 보인다. 그러나, 그럼에도 불구하고 이 최장 보로노이 다이어그램의 복잡도는 $O(nm^2)$ 이라는 것을 보인다. 이는 우리의 알고리즘보다 더 나은 시간 복잡도를 가지는 알고리즘이 존재를 예측한다.
