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.
트랜스포테이션 모델에서는 두 점 사이의 거리를 한 점에서 다른 점으로 갈 때 필요한 최소의 시간으로 측정한다. 이 학위논문은 유클리드 평면상에 이런 트랜스포테이션, 또는 교통수단이 주어졌을때에 보로노이 다이어그램에 대해 기하학적 그리고 알고리즘 적인 여러가지 성질과 특성에 대해 연구한다. 이와 같은 연구를 진행하는 과정에서 일반화된 보로노이 싸이트(Voronoi site)인 “바늘(needle)”을 소개하고 “바늘”이 트랜스포테이션 모델을 분석하고 설명하는 데에 매우 적합하다는 것을 보인다.
이 학위논문에서는 유클리드 평면상에 교통수단이 주어졌을 때에 보로노이 다이어그램을 계산하는 알고리즘을 제시한다. 이 알고리즘은 $O(nm^2 logn+ m^3 logm)$ 의 시간과 O(m(n+m))의 공간을 필요로 한다. 이 때, n은 주어진 싸이트(site)의 개수이고 m은 트랜스포테이션 안의 도로의 개수이다. 만약, 트랜스포테이션을 이루는 모든 도로들이 직각으로 만나고 또 x축 또는 y축과 평행하고, 모든 도로에서의 이동 속도가 같다고 가정하면, 같은 알고리즘으로 훨씬 빠른 시간인 $O(nm log n+ m^2 log m)$ 의 시간만에 보로노이 다이어그램을 계산할 수 있다. 또한, 이 때에는 다이어그램의 크기가 O(n+m)에 제한된다는 점을 주목할 만하다. 마지막으로, 트랜스포테이션 모델에서 “최단 거리 지도”(shortest path map)를 $O(m^3 logm)$ 의 시간 안에 계산할 수 있다는 것도 보였다.
