서지주요정보
Voronoi diagrams with transportation on the euclidean plane = 트랜스포테이션 모델에서의 보로노이 다이어그램
서명 / 저자 Voronoi diagrams with transportation on the euclidean plane = 트랜스포테이션 모델에서의 보로노이 다이어그램 / Sang-Won Bae.
저자명 Bae, Sang-Won ; 배상원
발행사항 [대전 : 한국과학기술원, 2004].
Online Access 원문보기 원문인쇄

소장정보

등록번호

8015298

소장위치/청구기호

학술문화관(문화관) 보존서고

MCS 04052

SMS전송

도서상태

이용가능

대출가능

반납예정일

초록정보

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)$ 의 시간 안에 계산할 수 있다는 것도 보였다.

서지기타정보

서지기타정보
청구기호 {MCS 04052
형태사항 v, 44 p. : 삽도 ; 26 cm
언어 영어
일반주기 저자명의 한글표기 : 배상원
지도교수의 영문표기 : Kyung-Yong Chwa
지도교수의 한글표기 : 좌경룡
학위논문 학위논문(석사) - 한국과학기술원 : 전산학전공,
서지주기 Reference : p. 43-44
주제 VORONOI DIAGRAM
TRANSPORTATION NETWORK
SHORTEST PATH
보로노이 다이어그램
도로망
최단 거리 경로
QR CODE qr code