請用此 Handle URI 來引用此文件：
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/20521完整後設資料紀錄
| DC 欄位 | 值 | 語言 |
|---|---|---|
| dc.contributor.advisor | 趙坤茂(Kun-Mao Chao) | |
| dc.contributor.author | Jia-Ming Zheng | en |
| dc.contributor.author | 鄭佳銘 | zh_TW |
| dc.date.accessioned | 2021-06-08T02:51:42Z | - |
| dc.date.copyright | 2020-09-03 | |
| dc.date.issued | 2020 | |
| dc.date.submitted | 2020-08-28 | |
| dc.identifier.citation | [1] M. Ajtai, J. Komlós, and E. Szemerédi. An o(n log n) sorting network. In D. S. Johnson, R. Fagin, M. L. Fredman, D. Harel, R. M. Karp, N. A. Lynch, C. H. Papadimitriou, R. L. Rivest, W. L. Ruzzo, and J. I. Seiferas, editors, Proceedings of the 15th Annual ACM Symposium on Theory of Computing, 2527 April, 1983, Boston, Massachusetts, USA, pages 1–9. ACM, 1983. [2] M. Basappa, R. K. Jallu, and G. K. Das. Constrained kcenter problem on a convex polygon. In O. Gervasi, B. Murgante, S. Misra, M. L. Gavrilova, A. M. A. C. Rocha, C. M. Torre, D. Taniar, and B. O. Apduhan, editors, Computational Science and Its Applications ICCSA 2015 15th International Conference, Banff, AB, Canada, June 2225, 2015, Proceedings, Part II, volume 9156 of Lecture Notes in Computer Science, pages 209–222. Springer, 2015. [3] B. Bhattacharya, A. Ćustić, S. Das, Y. Higashikawa, T. Kameda, and N. Katoh. Geometric center problems with centers constrained to two lines. In Discrete and computational geometry and graphs, volume 9943 of Lecture Notes in Comput. Sci., pages 24–36. Springer, Cham, 2016. [4] B. Bhattacharya, S. Das, T. Kameda, P. R. S. Mahapatra, and Z. Song. Optimizing squares covering a set of points. In Combinatorial optimization and applications, volume 8881 of Lecture Notes in Comput. Sci., pages 37–52. Springer, Cham, 2014. [5] P. Bose and Q. Wang. Facility location constrained to a polygonal domain. In S. Rajsbaum, editor, LATIN 2002: Theoretical Informatics, 5th Latin American Symposium, Cancun, Mexico, April 36, 2002, Proceedings, volume 2286 of Lecture Notes in Computer Science, pages 153–164. Springer, 2002. [6] T. M. Chan. More planar twocenter algorithms. Comput. Geom., 13(3):189–198, 1999. [7] D. Z. Chen, J. Li, and H. Wang. Efficient algorithms for the onedimensional k-center problem. Theoret. Comput. Sci., 592:135–142, 2015. [8] R. Cole. Slowing down sorting networks to obtain faster sorting algorithms. J. Assoc. Comput. Mach., 34(1):200–208, 1987. [9] T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein. Introduction to algorithms. MIT Press, Cambridge, MA, third edition, 2009. [10] H. Du and Y. Xu. An approximation algorithm for kcenter problem on a convex polygon. J. Comb. Optim., 27(3):504–518, 2014. [11] D. Eppstein. Faster construction of planar twocenters. In Proceedings of the Eighth Annual ACMSIAM Symposium on Discrete Algorithms (New Orleans, LA, 1997), pages 131–138. ACM, New York, 1997. [12] F. Hurtado, V. Sacristán, and G. Toussaint. Constrained facility location. Studies of Location Analysis, Special Issue on Computational Geometry, pages 15–17, 2000. [13] A. Karmakar, S. Das, S. C. Nandy, and B. K. Bhattacharya. Some variations on constrained minimum enclosing circle problem. J. Comb. Optim., 25(2):176–190, 2013. [14] N. Megiddo. Applying parallel computation algorithms in the design of serial algorithms. J. Assoc. Comput. Mach., 30(4):852–865, 1983. [15] N. Megiddo. Lineartime algorithms for linear programming in R3 and related problems. SIAM J. Comput., 12(4):759–776, 1983. [16] N. Megiddo and K. J. Supowit. On the complexity of some common geometriclocation problems. SIAM J. Comput., 13(1):182–196, 1984. [17] F. P. Preparata. New parallelsorting schemes. IEEE Trans. Comput., 27(7):669–673, 1978. [18] F. P. Preparata and M. I. Shamos. Computational geometry. Texts and Monographs in Computer Science. SpringerVerlag, New York, 1985. An introduction. [19] S. Roy, D. Bardhan, and S. Das. Base station placement on boundary of a convex polygon. J. Parallel Distributed Comput., 68(2):265–273, 2008. [20] M. I. Shamos. Computational Geometry. PhD thesis, Yale University, USA, 1978. AAI7819047. [21] X. Tan and B. Jiang. Simple O(n log2 n) algorithms for the planar 2center problem. In Computing and combinatorics, volume 10392 of Lecture Notes in Comput. Sci., pages 481–491. Springer, Cham, 2017. [22] H. Wang. On the planar twocenter problem and circular hulls, 2020. [23] H. Wang and J. Zhang. Lineconstrained kmedian, kmeans and kcenter problems in the plane. In Algorithms and computation, volume 8889 of Lecture Notes in Comput. Sci., pages 3–14. Springer, Cham, 2014. | |
| dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/20521 | - |
| dc.description.abstract | 在本論文中，我們的研究對象是平面上限制在兩條直線上的 k 中心問題。我們研究受限制版本的 k 中心問題的原因為，不受限制的 k 中心問題已被證明為 NP 困難。 我們首先介紹一項非常實用的技巧，稱作「參數化搜尋」，而後陸續介紹限制在單條直線上的 k 中心問題，以及限制在兩條特殊安排的 k 中心問題，包括兩條平行線與兩條垂直線。這些問題激發我們對任意相交直線的 k 中心問題的解法。雖然在後來發現欲解的問題缺少足夠好的性質能夠被利用來完全解決問題，我們仍透過削減少許區域，成功辨識出一個有意義的特殊狀況。最終我們得到一個 O (n log2 n) 的演算法。 | zh_TW |
| dc.description.abstract | In this thesis, we study the k-centre problem in the plane with the constraint that the centres should lie in two lines. We study the constrained version of the k-centre problem because the unconstrained k-centre problem has been proved to be NP-hard. We first introduce an extraordinarily useful technique called “parametric search”, and then review the k-centre problem constrained to a single line and the k-centre problems constrained to two lines of special arrangement, including two parallel lines and two perpendicular lines, which stimulate our solution for k-centre problem constrained on arbitrarily intersecting lines. Though we later discover a deficiency of good property needed to be exploited to solve the problem perfectly, we still succeed in the identification of a meaningful special case by removing a small fraction of area. We attain an algorithm which runs in O (n log2 n) . | en |
| dc.description.provenance | Made available in DSpace on 2021-06-08T02:51:42Z (GMT). No. of bitstreams: 1 U0001-2508202018150800.pdf: 606457 bytes, checksum: 5e72df7229c4cc5523220d83bb6b4e3f (MD5) Previous issue date: 2020 | en |
| dc.description.tableofcontents | 口試委員會審定書 iii 摘要 v Abstract vii 1 Introduction 1 1.1 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 2 Preliminary 5 2.1 Model of Computation . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 2.2 Parametric Searching . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 2.2.1 Searching for the Extreme value . . . . . . . . . . . . . . . . . . 8 2.3 Line-Constrained Fixed Cost Covering Problem . . . . . . . . . . . . . . 9 2.4 LineConstrained k-Centre Problem . . . . . . . . . . . . . . . . . . . . 10 2.4.1 The Unweighted Case . . . . . . . . . . . . . . . . . . . . . . . 10 2.4.2 The Weighted Case . . . . . . . . . . . . . . . . . . . . . . . . . 11 3 Algorithms for Constrained Planar k-Centre Problems 13 3.1 Centres Constrained to Two Parallel Lines . . . . . . . . . . . . . . . . . 13 3.2 Centres Constrained to Two Perpendicular Lines . . . . . . . . . . . . . 19 3.3 Centres Constrained to Two Crossing Lines . . . . . . . . . . . . . . . . 23 4 Conclusion 29 Bibliography 31 | |
| dc.language.iso | en | |
| dc.title | 二維兩直線上個中心的設置問題 | zh_TW |
| dc.title | The -Centre Problem in the Plane with Centres Constrained to Two Lines | en |
| dc.type | Thesis | |
| dc.date.schoolyear | 108-2 | |
| dc.description.degree | 碩士 | |
| dc.contributor.oralexamcommittee | 王弘倫(Hung-Lung Wang),朱安強(An-Chiang Chu),吳彥緯(Yen-Wei Wu) | |
| dc.subject.keyword | 計算幾何,參數化搜尋,k中心問題,受限制k中心問題,設施設置問題,最佳化問題, | zh_TW |
| dc.subject.keyword | Computational geometry,parametric search,-centre problem,constrained -centre problem,facility location problem,optimisation problem, | en |
| dc.relation.page | 33 | |
| dc.identifier.doi | 10.6342/NTU202004168 | |
| dc.rights.note | 未授權 | |
| dc.date.accepted | 2020-08-28 | |
| dc.contributor.author-college | 電機資訊學院 | zh_TW |
| dc.contributor.author-dept | 資訊工程學研究所 | zh_TW |
| 顯示於系所單位： | 資訊工程學系 | |
文件中的檔案：
| 檔案 | 大小 | 格式 | |
|---|---|---|---|
| U0001-2508202018150800.pdf 目前未授權公開取用 | 592.24 kB | Adobe PDF |
系統中的文件，除了特別指名其著作權條款之外，均受到著作權保護，並且保留所有的權利。