兩條高速公路下的時間凸多邊形結構

Abstract

在這裡我們考慮了一個兩條高速公路下的時間凸多邊形結構的問題，在這個問題底下我們給定了n個點及兩條筆直的高速公路，這兩條高速公路在圖形上可表示成兩條直線，而在高速公路上的移動速度遠大於在平面上的移動速度，而我們所要求的就是以時間為考量下所做的凸多邊形結構問題。 在此問題底下，所有的相異點的最短時間路徑一定是一條直線或是通過高速公路的一條路徑，也就是說除非走高速公路所花的時間比直線來的少才會選擇走高速公路。 對於給定n個點的點集合P時間凸多邊形在這裡記做CHt(P)，定義為最小的集合來完全包含自己，在這樣的集合裡，任意兩個點的最短時間路徑也一定座落於CHt(P)內，對於這樣的凸多邊形即為對於點集合P的時間凸多邊形。 在這篇論文中我們給了一個時間複雜度為θ(n log n)的演算法來去解決這個問題。

We consider the problem of computing the time convex hull of a set of n points in the presence of two straight-line highways in the plane. The traveling speed in the plane is assumed to be much slower than that along the highways. The shortest time path between two arbitrary points is either the straight-line segment connecting these two points or a path that passes through the highway(s). The time convex hull, CHt(P), of a set P of n points is the smallest set containing P such that all the shortest time paths between any two points lie in CHt(P). In this thesis we give a θ(n log n) time algorithm for solving the time convex hull problem for a set of n points in the presence of two highways.