This thesis considers algorithmic problems on geometric transportation network, motivated by the real-world transportation networks, in a computational point of view.
In a city or anywhere on this planet, people use transportation networks like streets in a city, subway or bus networks, or a highway over a nation. Such a transportation network supports faster movement and help in economizing travel time.
We define a $\emph{transportation network}$ as a (straight-line) plane graph with edges assigned by positive real numbers, called speeds. By certain rules of using a given transportation network, the travel time for each path is well defined, and thus a new metric, called a $\emph{transportation metric}$, is induced.
This thesis introduces several interesting research problems arising in this situation; some of those are shortest (or quickest) paths problem, Voronoi diagrams, farthest Voronoi diagram, transportation network design problems, and so on. These problems are roughly categorized into $\emph{proximity problems}$ and $\emph{location problems}$. In this thesis, we define such problems that we consider, present a number of new results on those problems, and finally conclude with future work and interesting open questions.
본 논문은 현실 세계의 도로망에서 동기를 얻은 트랜스포테이션 네트워크에서 발생하는 문제들을 계산이론적 관점에서 다룬다.
도시나 혹은 이 지구상 어디에서든 인간들은 도로, 지하철이나 버스 네트워크, 혹은 한 나라의 고속도로와 같은 트랜스포테이션 네트워크를 수시로 사용하고 있다. 이런 트랜스포테이션 네트워크는 더 빠른 이동을 할 수 있게 해주고, 그로 인해 이동시간을 절약하는 데에 도움을 준다.
본 논문에서는 ″트랜스포테이션 네트워크 (transportation network)″를 각 간선에 속도가 부여된 (직선)평면그래프로 정의한다. 트랜스포테이션 네트워크는 그것을 사용하는 데에 필요한 특정한 규칙과 함께, 평면상의 모든 경로에 대해 이동시간을 잘 정의해주며, 그리하여 새로운 거리개념인 ″트랜스포테이션 거리 (transportation metric)″가 유도된다.
본 논문은 이런 상황 하에서 발생하는 수 가지 흥미로운 연구 문제를 제기한다. 최단 (시간) 경로 문제, 보로노이 다이어그램, 최장 보로노이 다이어그램, 트랜스포테이션 네트워크 설계 문제 등이 그것이며, 이러한 문제들은 크게 근접성 문제와 배치 문제로 분류될 수 있다. 본 논문에서는 다루게 될 문제들을 정의하고 여러 새로운 연구결과를 제시하며 마지막으로 이후 연구 주제와 아직 해결되지 못한 흥미로운 연구 문제들을 소개한다.
