臺灣博碩士論文加值系統

在這裡我們考慮了一個兩條高速公路下的時間凸多邊形結構的問題，在這個問題底下我們給定了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.

Contents
口試委員會審定書
誌謝 i
Chinese Abstract ii
English Abstract iii
1 Introduction 1
2 Preliminaries 2
2.1 Definition 2
2.2 Previous Work 4
3 Two Infinite-Speed Highways Model 7
3.1 Preprocessing 9
3.2 Finding Clusters 10
3.3 Constructing the Time Convex Hull 19
3.4 Timing Analysis 20
4 Two Highways with Same Bounded Speed Model 21
4.1 Preprocessing 24
4.2 Finding Clusters 29
4.3 Constructing Time Convex Hull 34
4.4 Timing Analysis . 34
5 Two General Highways Model 34
5.1 Preprocessing 35
5.2 Finding Clusters 36
5.3 Constructing Time Convex Hull 36
5.4 Timing Analysis 37
6 Conclusion 37
References 38

[1] M. Abellanas, F. Hurtado, C. Icking, R. Klein, E. Langetepe, L. Ma, B. Palop, and V. Sacrist’an. Proximity problems for time metrics induced by the l1 metric and isothetic networks. IX Encuetros en Geometria Computacional, 2001.
[2] M. Abellanas, F. Hurtado, B. Palop. Transportation networks and voronoi digrams. Proc. of International Symposium on Voronoi Diagrams in Science and Engineering, September 2004, 203-212.
[3] M. Abellanas, F. Hurtado, V. Sacrist´an, C. Icking, L. Ma, R. Klein, E. Langetepe, B. Palop. Voronoi digram for services neighboring a highway. Information Processing Letters 86 (2003) 283-288.
[4] O. Aichholzer, F. Aurenhammer, D. Z. Chen, D.T. Lee and E. Papadopoulou. Skew Voronoi Diagram. Int’l J. Comput. Geometry and Apllications, 9(3), June 1999, pp. 235-248.
[5] S. W. Bae and K.-Y. Chwa. Voronoi diagrams with a transportation network on the euclidean plane. Technical report, Korea Advanced Institute of Science and Technology, 2005. A preliminary version appeared in proceedings of ISAAC 2004.
[6] S. W. Bae and K.-Y. Chwa. Shortest Paths and Voronoi Diagrams with Transportation Networks Under General Distances. Algorithms and Computation: 16th International Symposium, ISAAC 2005, Sanya, Hainan, China, December 19-21, 2005.
[7] R. L. Graham. An efficient algorithm for determining the convex hull of a finite planar set. Inform. Process. Lett., 1:132-133, 1972.
[8] D.T. Lee. Two Dimensional Voronoi Diagram in the Lp-metric. J. ACM, Oct. 1980, 604-618.
[9] D.T. Lee and R. L. Drydale. Generalization of Voronoi Diagram in the Plane.SIAM J. Comput. Feb. 1981, 73-87.
[10] D.T. Lee, Chung-Shou Liao, and Wei-Bung Wang. Time-Based Voronoi Diagram. Proc. of International Symposium on Voronoi Diagrams in Science and Engineering, September 2004, 229-243.
[11] B. Palop. Algorithmic problems on proximity and location under metric constraints. PhD thesis, Universitat Polit`ecnica de Catalunya, 2003.
[12] E. Papadopoulou and D.T. Lee. A New Approach for the Geodesic Voronoi Diagram of Points in a Simple Polygon and Other Restricted Polygonal Domains. Algorithm, 20(4), April 1998, 319-352.
[13] F. P. Preparata, D. E. Muller. Finding the Intersection of n Half-Spaces in Time O(n log n). Theor. Comput. Sci. 8: 45-55 (1979).
[14] Franco P. Preparata, Micheal Ian Shamos. Computational Geometry An Introduction, Springer.
[15] T. K. Yu and D. T. Lee, Time Convex Hull with a Highway, Proc. 4th ISVD Int’l Symp. Voronoi Diagrams in Science and Engineering (ISVD 2007), Wales, UK, July 2007.