臺灣博碩士論文加值系統

在這份學位論文中，我們從演算法的角度來探討工業應用上的幾何計算問題。這些在工業設計、製造與管理領域中所遭遇到的實際問題被我們以數學模型抽象化的方式規劃成正式的演算法問題。針對這些工業應用上的幾何計算問題，我們分別提出了具有理論作為保證的演算法設計分析與問題困難度的論證、以及從組合數學的面向去探討組合學複雜度，共同構成在這個複雜議題上一份完整且全面性的研究探討。
在工業設計和製造方面，我們考慮了“固體鑄模”問題，這個問題是從鑄模技術的設計程序以及製造程序中許多的最佳化問題所規劃出來。從理論的觀點來看，我們所探討的固體鑄模問題在“計算幾何”領域中一個最古典的研究主題“可視性”裡是相當重要且具有基礎性的議題。針對此問題，我們分別提出了具備嚴謹理論作為保證的演算法設計分析以及問題困難度的證明，在我們獲得的主要研究成果中，問題複雜度與演算法複雜度之間的間隔差距幾乎是封閉的。此外，從組合數學的角度，我們也提出了緊貼的組合學複雜度上界與下界。在實務應用上，我們所設計的演算法相當有效率。
在工業管理方面，我們考慮了“時間凸包”問題，這個問題是由在高速運輸網路存在的情況之下的“路徑規劃”議題及最短路徑問題的進階延伸所引起。對於運輸業而言，將運輸時間與運輸成本最小化是最重要的追求目標之一。在這個問題中，我們探討了最短時間成本的路徑規劃以及“凸包”問題在被導入以“時間”為基礎的概念之下的問題推廣。針對此問題，我們獲得的主要研究成果是在一條直線高速公路存在的情況裡，並且以廣義Lp作為距離的度量底下，一個能透過理論證明為最佳的演算法。就某種意義上，我們的研究成果終結了此問題在這樣的特定網路拓樸底下的研究探討。

This dissertation addresses the geometric computing problems in industrial application from an algorithmic perspective. The practical issues encountered in the fields of industrial design, manufacturing, and management are formulated as algorithmic problems by mathematical abstraction. We present both the algorithmic results and the hardness proofs with theoretical guarantees and also the combinatorial bounds in the aspect of combinatorics to jointly compose a comprehensive study for the entire research.

In terms of industrial design and manufacturing, we consider the solid moulding problem, which is formulated from the optimization point of view in the design and manufacturing process of moulding technology. From the theoretical perspective, the solid moulding problem is also fundamental in visibility, one of the most classical topics in computational geometry. We present both the algorithmic results and the hardness proofs for the problems addressed in this dissertation, and the gap between the problem complexity and the algorithm complexity contained in our main results is nearly closed. In the aspect of combinatorics, we provide the tight combinatorial bounds. Our algorithms are efficient in practice.

In terms of industrial management, we consider the time convex hull problem, which arises from path planning and further extensions of the shortest path problem, in the presence of high-speed transportation networks. For transportation business, to minimize the transportation time and cost is among the most important objectives. We explore shortest time-path planning and the generalization of convex hull into which the time-based concept is introduced. The main result is an optimal time algorithm for the problem under the general Lp metrics, in the presence of a straight-line highway. Our results in some sense have closed the study of this problem in the particular network topology.

致謝 i
摘要 ii
Abstract iii
1 Background and Motivation 1
2 Geometric Computing Problems 6
2.1 Introduction to Solid Moulding Problem 6
2.1.1 Problem Definition 6
2.1.2 State of the Art 8
2.1.3 Summary of the Results Obtained 10
2.2 Introduction to Time Convex Hull Problem 11
2.2.1 Problem Definition 11
2.2.2 State of the Art 12
2.2.3 Summary of the Results Obtained 14
3 Solid Moulding Problem 16
3.1 Fundamental Lemmas and Theorems 16
3.2 An Optimal Algorithm for the Dark Boundary Problem 21
3.3 The Prerequisite of the Optimal Moulding Problem 22
3.4 Combinatorial Bounds 24
3.5 Problem Complexity 25
3.6 Computing the IA Intervals in Optimal Linear Time 30
3.7 The Preprocessing Algorithm for the Optimal Moulding Problem 36
3.7.1 Removing the Redundant IA Intervals of Points on the Same Edge 37
3.7.2 Retaining Exactly One IA Interval of the Minimum Ending Angle from those with the Same Beginning Angle 38
3.7.3 Removing the Redundant IA Intervals with Distinct Beginning Angles 44
3.8 The Main Algorithm 47
3.8.1 Computing the Successor Angle Function 50
3.8.2 Computing the Local Optimal Solutions 53
3.8.3 Finding an Optimal Solution 60
3.8.4 A Variant of the Optimal Moulding Problem under Pairs of Antipodal Parallel Beams 61
4 Time Convex Hull Problem 64
4.1 Fundamental Lemmas and Theorems 64
4.1.1 Convexity and time-convex hulls 65
4.1.2 Time-convex hull under the L1 and the L2 metrics 65
4.2 Hull-Structure under the General Lp-Metrics 66
4.2.1 Wavefronts and Shortest Time-Paths 67
4.2.2 Walking Regions 73
4.2.3 Closure and Time-Convex Hull of a Point Set 77
4.3 Constructing the Time-Convex Hull 78
4.3.1 Problem Complexity 79
4.3.2 An Optimal Algorithm 79
5 Conclusions and Future Work 84
5.1 Summary and Discussion 84
5.2 Future Work 86
Bibliography 88

[1] M. Abellanas, F. Hurtado, Sacrist an, C. Icking, L. Ma, R. Klein, E. Langetepe, and B. Palop, Voronoi diagram for services neighboring a high-way, Inf. Process. Lett., 86(5) (2003), pp. 283-288.
[2] P. Agarwal and M. Sharir, Davenport-Schinzel Sequences and Their Geometric Applications, Cambridge University Press, 1995.
[3] P. Agarwal, M. Sharir, and P. Shor, Sharp upper and lower bounds on the length of general davenport-schinzel sequences, Journal of Combinatorial Theory,
Series A, 52(2) (1989), pp. 228-274.
[4] O. Aichholzer, F. Aurenhammer, and B. Palop, Quickest paths, straight skeletons, and the city voronoi diagram, in Proceedings of the eighteenth annual symposium on Computational geometry, SCG ''02, New York, NY, USA, 2002, ACM, pp. 151-159.
[5] G. Aloupis, J. Cardinal, S. Collette, F. Hurtado, S. Langerman, J. O''Rourke, and B. Palop, Highway hull revisited, Comput. Geom. Theory Appl., 43 (2010), pp. 115-130.
[6] M. H. Alsuwaiyel and D. T. Lee, Finding an approximate minimum-link visibility path inside a simple polygon, Inf. Process. Lett., 55 (1995), pp. 75-79.
[7] E. M. Arkin, J. S. B. Mitchell, and C. D. Piatko, Minimum-link watchman tours, Inf. Process. Lett., 86 (2003), pp. 203-207.
[8] B. Aronov, E. Ezra, and M. Sharir, Small-size-nets for axis-parallel rectangles and boxes, in Proceedings of the Forty- rst Annual ACM Symposium on Theory of Computing, STOC ''09, New York, NY, USA, 2009, ACM, pp. 639-648.
[9] D. Avis, T. Gum, and G. T. Toussaint, Visibility between two edges of a simple polygon, The Visual Computer, 2 (1986), pp. 342-357.
[10] D. Avis and G. T. Toussaint, An optimal algorithm for determining the visibility of a polygon from an edge, IEEE Trans. Computers, 30 (1981), pp. 910-914.
[11] S. W. Bae and K.-Y. Chwa, Shortest paths and voronoi diagrams with transportation networks under general distances, in Proceedings of the 16th International
Conference on Algorithms and Computation, ISAAC''05, Berlin, Heidelberg, 2005, Springer-Verlag, pp. 1007-1018.
[12] S. W. Bae, J.-H. Kim, and K.-Y. Chwa, Optimal construction of the city voronoi diagram, in Proceedings of the 17th international conference on Algorithms and
Computation, ISAAC''06, Berlin, Heidelberg, 2006, Springer-Verlag, pp. 183-192.
[13] M. Ben-Or, Lower bounds for algebraic computation trees, in Proceedings of STOC''83, 1983, pp. 80-86.
[14] I. Bjorling-Sachs, Edge guards in rectilinear polygons, Computational Geometry, 11 (1998), pp. 111-123.
[15] P. Bose and G. T. Toussaint, Geometric and computational aspects of manufacturing processes, Computers &; Graphics, 18 (1994), pp. 487-497.
[16] H. Bronnimann and M. T. Goodrich, Almost optimal set covers in finite vc-dimension: (preliminary version), in Proceedings of the Tenth Annual Symposium on Computational Geometry, SCG ''94, New York, NY, USA, 1994, ACM, pp. 293-302.
[17] J. Cardinal, S. Collette, F. Hurtado, S. Langerman, and B. Palop, Optimal location of transportation devices, Computational Geometry, 41 (2008), pp. 219-229.
[18] S. Carlsson, H. Jonsson, and B. J. Nilsson, Finding the shortest watchman route in a simple polygon, Discrete &; Computational Geometry, 22 (1999), pp. 377-402.
[19] T. M. Chan, Polynomial-time approximation schemes for packing and piercing fat objects, Journal of Algorithms, 46 (2003), pp. 178-189.
[20] T. M. Chan and A.-A. Mahmood, Approximating the piercing number for unit-height rectangles., in CCCG, 2005, pp. 15-18.
[21] B. Chazelle, Triangulating a simple polygon in linear time, Discrete &; Computational Geometry, 6(1) (1991), pp. 485-524.
[22] B. Chazelle and L. J. Guibas, Visibility and intersection problems in plane geometry, Discrete &; Computational Geometry, 4 (1989), pp. 551-581.
[23] D. Z. Chen, An optimal parallel algorithm for detecting weak visibility of a simple polygon, in Proceedings of the Eighth Annual Symposium on Computational Geometry, SCG ''92, New York, NY, USA, 1992, ACM, pp. 63-72.
[24] L.-L. Chen, S.-Y. Chou, and T. C. Woo, Parting directions for mould and die design, Computer-Aided Design, 25(12) (1993), pp. 762-768.
[25] W.-P. Chin and S. Ntafos, Optimum watchman routes, Information Processing Letters, 28 (1988), pp. 39-44.
[26] W.-P. Chin and S. Ntafos, Shortest watchman routes in simple polygons, Discrete &; Computational Geometry, 6 (1991), pp. 9-31.
[27] B.-S. Dai, M.-J. Kao, and D. T. Lee, Optimal time-convex hull under the Lp metrics, in Algorithms and Data Structures, vol. 8037 of Lecture Notes in Computer
Science, Springer Berlin Heidelberg, 2013, pp. 268-279.
[28] H. Edelsbrunner, J. O''Rourke, and E. Welzl, Stationing guards in rectilinear art galleries, Computer Vision, Graphics, and Image Processing, 27 (1984), pp. 167-176.
[29] S. Eidenbenz, Inapproximability results for guarding polygons without holes, ISAAC, (1998), pp. 427-436.
[30] S. Eidenbenz, Approximation algorithms for terrain guarding, Inf. Process. Lett., 82 (2002), pp. 99-105.
[31] S. Eidenbenz, C. Stamm, and P. Widmayer, Inapproximability results for guarding polygons and terrains, Algorithmica, 31 (2001), pp. 79-113.
[32] H. A. ElGindy and D. Avis, A linear algorithm for computing the visibility polygon from a point, J. Algorithms, 2 (1981), pp. 186-197.
[33] T. Feder and D. Greene, Optimal algorithms for approximate clustering, in Proceedings of the Twentieth Annual ACM Symposium on Theory of Computing, STOC ''88, New York, NY, USA, 1988, ACM, pp. 434-444.
[34] R. Fowler, M. Paterson, and S. Tanimoto, Optimal packing and covering in the plane are np-complete, Inform. Process. Lett., 12(3) (1981), pp. 133-137.
[35] M. Fu, A. Nee, and J. Fuh, The application of surface visibility and moldability to parting line generation, Computer-Aided Design, 34 (2002), pp. 469-480.
[36] A. Gemsa, D. T. Lee, C.-H. Liu, and D. Wagner, Higher order city voronoi diagrams, in Algorithm Theory SWAT 2012, vol. 7357 of Lecture Notes in Computer Science, Springer Berlin Heidelberg, 2012, pp. 59-70.
[37] S. K. Ghosh, Computing the visibility polygon from a convex set and related problems, J. Algorithms, 12 (1991), pp. 75-95.
[38] S. K. Ghosh, Approximation algorithms for art gallery problems in polygons, Discrete Applied Mathematics, 158(6) (2010), pp. 718-722.
[39] T. F. Gonzalez, Covering a Set of Points in Multidimensional Space, Information Processing Letters, 40 (1991), pp. 181-188.
[40] M. T. Goodrich, S. B. Shauck, and S. Guha, Parallel methods for visibility and shortest path problems in simple polygons (preliminary version), in Proceedings of the Sixth Annual Symposium on Computational Geometry, SCG ''90, New York, NY, USA, 1990, ACM, pp. 73-82.
[41] L. Guibas, J. Hershberger, D. Leven, M. Sharir, and R. E. Tarjan, Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygons, Algorithmica, 2 (1987), pp. 209-233.
[42] L. Guibas, J. Hershberger, and J. Snoeyink, Compact interval trees: a data structure for convex hulls, in Proceedings of SODA''90, 1990, pp. 169-178.
[43] U. I. Gupta, D. T. Lee, and J. Y.-T. Leung, E cient algorithms for interval graphs and circular-arc graphs, NETWORKS, 12 (1982), pp. 459-467.
[44] E. Gyri, F. Hoffmann, K. Kriegel, and T. Shermer, Generalized guarding and partitioning for rectilinear polygons, Computational Geometry, 6 (1996), pp. 21-44.
[45] S. Hart and M. Sharir, Nonlinearity of davenport-schinzel sequences and of generalized path compression schemes, Combinatorica, 6(2) (1986), pp. 151-177.
[46] P. J. Heffernan and J. S. B. Mitchell, An optimal algorithm for computing visibility in the plane, WADS, (1991), pp. 437-448.
[47] J. Hershberger, Finding the upper envelope of n line segments in o(n log n) time, Inform. Process. Lett., 33(4) (1989), pp. 169-174.
[48] D. S. Hochbaum and W. Maass, Approximation schemes for covering and packing problems in image processing and vlsi, J. ACM, 32 (1985), pp. 130-136.
[49] C. M. Hoffmann, Geometric and Solid Modeling: An Introduction, Morgan Kaufmann, 1989.
[50] F. Hoffmann, On the rectilinear art gallery problem, in Automata, Languages and Programming, M. Paterson, ed., vol. 443 of Lecture Notes in Computer Science, Springer Berlin Heidelberg, 1990, pp. 717-728.
[51] F. Hoffmann, M. Kaufmann, and K. Kriegel, The art gallery theorem for polygons with holes, FOCS, (1991), pp. 39-48.
[52] K. C. Hui, Geometric aspects of the mouldability of parts, Computer-Aided Design, 29 (1997), pp. 197-208.
[53] K. C. Hui and S. T. Tan, Mould design with sweep operations a heuristic search approach, Computer-Aided Design, 24 (1992), pp. 81-91.
[54] F. Hurtado, B. Palop, and V. Sacrist an, Diagramas de voronoi con distancias temporales, Actas de los VIII Encuentros de Geometra Computacional, 1999, pp. 279-288. in Spanish.
[55] M. J. Katz and G. S. Roisman, On guarding the vertices of rectilinear domains, Computational Geometry, 39 (2008), pp. 219-228.
[56] D. O. Kazmer, Injection Mold Design Engineering, Hanser Verlag, 2007.
[57] M. Korman and T. Tokuyama, Optimal insertion of a segment highway in a city metric, in Proceedings of the 14th Annual International Conference on Computing and Combinatorics, COCOON ''08, Berlin, Heidelberg, 2008, Springer-Verlag, pp. 611-620.
[58] D. T. Lee, On nding the convex hull of a simple polygon, International Journal of Computer and Information Sciences, 12(2) (1983), pp. 87-98.
[59] D. T. Lee, Visibility of a simple polygon, Computer Vision, Graphics, and Image Processing, 2 (1983), pp. 186-197.
[60] D. T. Lee, C.-S. Liao, and W.-B. Wang, Time-based voronoi diagram, in Proc. of International Symposium on Voronoi Diagrams in Science and Engineering, 2004, pp. 229-243.
[61] D. T. Lee and A. K. Lin, Computational complexity of art gallery problems, IEEE Transactions on Information Theory, 32 (1986), pp. 276-282.
[62] D. T. Lee and A. K. Lin, Computing the visibility polygon from an edge, Computer Vision, Graphics, and Image Processing, 34 (1986), pp. 1-19.
[63] D. McCallum and D. Avis, A linear algorithm for nding the convex hull of a simple polygon, Inform. Process. Lett., 9(5) (1979).
[64] A. A. Melkman, On-line construction of the convex hull of a simple polyline, Inform. Process. Lett., 25 (1987), pp. 11-12.
[65] T. S. Michael and V. Pinciu, Art gallery theorems for guarded guards, Comput. Geom., 26 (2003), pp. 247-258.
[66] F. Nielsen, Fast stabbing of boxes in high dimensions, Theoretical Computer Science, 246 (2000), pp. 53-72.
[67] B. Nilsson, Approximate guarding of monotone and rectilinear polygons, in Automata, Languages and Programming, L. Caires, G. Italiano, L. Monteiro,
C. Palamidessi, and M. Yung, eds., vol. 3580 of Lecture Notes in Computer Science, Springer Berlin Heidelberg, 2005, pp. 1362-1373.
[68] J. O''Rourke, An alternate proof of the rectilinear art gallery theorem, Journal of Geometry, 21 (1983), pp. 118-130.
[69] J. O''Rourke, Art Gallery Theorems and Algorithms, Oxford University Press, 1987.
[70] J. O''Rourke and I. Streinu, The vertex-edge visibility graph of a polygon, Computational Geometry, 10 (1998), pp. 105-120.
[71] T. Ottmann, E. Soisalon-Soininen, and D. Wood, On the de nition and computation of rectilinear convex hulls, Information Sciences, 33 (1984), pp. 157-171.
[72] J. Pach and G. Tardos, Tight lower bounds for the size of epsilon-nets, in Proceedings of the Twenty-seventh Annual Symposium on Computational Geometry, SoCG ''11, New York, NY, USA, 2011, ACM, pp. 458-463.
[73] B. Palop, Algorithmic Problems on Proximity and Location under Metric Constraints, PhD thesis, Universitat Polit ecnica de Catalunya, 2003.
[74] J.-R. Sack and S. Suri, An optimal algorithm for detecting weak visibility of a polygon, IEEE Trans. Computers, 39 (1990), pp. 1213-1219.
[75] D. Schuchardt and H.-D. Hecker, Two np-hard art-gallery problems for ortho-polygons, Mathematical Logic Quarterly, 41 (1995), pp. 261-267.
[76] T. C. Shermer, Recent results in art galleries, Proceedings of the IEEE, 80 (1992).
[77] X. Tan, Fast computation of shortest watchman routes in simple polygons, Information Processing Letters, 77 (2001), pp. 27-33.
[78] G. T. Toussaint, A linear-time algorithm for solving the strong hidden-line problem in a simple polygon, Pattern Recogn. Lett., 4 (1986), pp. 449-451.
[79] G. T. Toussaint, Shortest path solves edge-to-edge visibility in a polygon, PRL, (1986), pp. 165-170.
[80] J. Urrutia, Art gallery and illumination problems, Handbook of computational
geometry, (2000).
[81] Z. P. Yin, H. Ding, and Y. L. Xiong, Virtual prototyping of mold design: geometric mouldability analysis for near-net-shape manufactured parts by feature recognition and geometric reasoning, Computer-Aided Design, 33 (2001), pp. 137-154.
[82] T.-K. Yu and D. T. Lee, Time convex hull with a highway, in Proceedings of the 4th International Symposium on Voronoi Diagrams in Science and Engineering, ISVD ''07, Washington, DC, USA, 2007, IEEE Computer Society, pp. 240-250.