請用此 Handle URI 來引用此文件：
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/54456完整後設資料紀錄
| DC 欄位 | 值 | 語言 |
|---|---|---|
| dc.contributor.advisor | 趙坤茂(Kun-Mao Chao) | |
| dc.contributor.author | Albert Jhih-Heng Huang | en |
| dc.contributor.author | 黃志恒 | zh_TW |
| dc.date.accessioned | 2021-06-16T02:57:58Z | - |
| dc.date.available | 2017-09-30 | |
| dc.date.copyright | 2015-09-30 | |
| dc.date.issued | 2015 | |
| dc.date.submitted | 2015-07-07 | |
| dc.identifier.citation | [1] P. K. Agarwal and M. Sharir. Planar geometric location problems. Algorithmica,
11(2):185–195, 1994. [2] P. K. Agarwal, M. Sharir, and E. Welzl. The discrete 2-center problem. Discrete and Computational Geometry, 20(3):287–305, 1998. [3] B. Ben-Moshe, B. Bhattacharya, and Q. Shi. An optimal algorithm for the continuous/ discrete weighted 2-center problem in trees. Latin American Theoretical Informatics, pages 166–177, 2006. [4] B. Bhattacharya and Q. Shi. Optimal algorithms for the weighted p-center problems on the real line for small p. Workshop on Algorithms and Data Structures, pages 529–540, 2007. [5] P. Bose and Q. Wang. Facility location constrained to a polygonal domain. Latin American Theoretical Informatics, pages 153–164, 2002. [6] P. Brass, C. Knauer, H.-S. Na, C.-S. Shin, and A. Vigneron. The aligned k-center problem. International Journal of Computational Geometry and Applications, 21(2): 157–178, 2011. [7] T. M. Chan. More planar two-center algorithms. Computational Geometry, 13:189– 198, 1999. [8] Z. Drezner. The planar two-center and two-median problems. Transportation Science, 18:351–361, 1984. [9] M. E. Dyer. On a multidimensional search technique and its application to the euclidean one-centre problem. SIAM Journal on Computing, 15(3):725–738, 1986. [10] M. E. Dyer and A. M. Frieze. A simple heuristic for the p-centre problem. Operations Research Letters, 3:285––288, 1985. [11] D. Eppstein. Faster construction of planar two-centers. Symposium on Discrete Algorithms, pages 131–138, 1997. [12] T. Feder and D. H. Greene. Optimal algorithms for approximate clustering. Symposium on the Theory of Computing, pages 434–444, 1988. [13] R. J. Fowler, M. S. Paterson, and S. L. Tanimoto. Optimal packing and covering in the plane are np-complete. Information Processing Letters, 12:133––137, 1981. [14] M. Hoffmann. A simple linear algorithm for computing rectilinear 3-centers. Computational Geometry, 31(3):150–165, 2005. [15] F. Hurtado, V. Sacristn, and G. Toussiant. Some constrainted minimax and maxmin location problems. Studies in Location Analysis, 5:17–35, 2000. [16] R. Z. Hwang, R. C. Chang, and R. C. T. Lee. The searching over separators strategy to solve some np-hard problems in subexponential time. Algorithmica, 9(4):398– 423, 1993. [17] J. W. Jaromczyk and M. Kowaluk. An efficient algorithm for the euclidean twocenter problem. Symposium on Computational Geometry, pages 303–311, 1994. [18] A. Karmakar, S. Das, S. C. Nandy, and B. Bhattacharya. Some variations on constrained minimum enclosing circle problem. Journal of Combinatorial Optimization, 25(2):176–190, 2013. [19] M. J. Katz and M. Sharir. An expander-based approach to geometric optimization. Symposium on Computational Geometry, pages 198–207, 1993. [20] S. K. Kim and C.-S. Shin. Efficient algorithms for two-center problems for a convex polygon. Computing and Combinatorics, pages 299–309, 2000. [21] A. Marchetti-Spaccamela. The p-center problem in the plane is np-complete. In Proceedings of the 19th Annual Allerton Conference on Communication, Control, and Computing, pages 31–40, 1981. [22] S. Masuyama, T. Ibaraki, and T. Hasegawa. The computational complexity of them- center problems on the plane. Trasaction on the Institute of Electronic, Information and Communication Engineers, E64(2):57–64, 1981. [23] N. Megiddo. Combinatorial optimization with rational objective functions. Symposium on the Theory of Computing, pages 1––12, 1978. [24] N. Megiddo. Applying parallel computation algorithms in the design of serial algorithms. Journal of the ACM, 30(4):852–865, 1983. [25] N. Megiddo. Linear-time algorithms for linear programming in r3 and related problems. SIAM Journal on Computing, 12(4):759–776, 1983. [26] N. Megiddo. The weighted euclidean 1-center problem. Mathematics of Operations Research, 8:498–504, 1983. [27] N. Megiddo. Linear programming in linear time when the dimension is fixed. Journal of the ACM, 31(1):114–127, 1984. [28] N. Megiddo and K. J. Supowit. On the complexity of some common geometric location problem. SIAM Journal on Computing, 13(1):182–196, 1984. [29] N. Megiddo and E. Zemel. An O(n log n) randomizing algorithm for the weighted euclidean 1-center problem. Journal of Algorithms, 7(3):358–368, 1986. [30] M. Sharir. A near-linear algorithm for the planar 2-center problem. Discrete and Computational Geometry, 18(2):125–134, 1997. [31] H. Wang and J. Zhang. Line-constrained k-median, k-means, and k-center problems in the plane. International Symposium on Algorithms and Computation, pages 3–14, 2014. | |
| dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/54456 | - |
| dc.description.abstract | 給定一個點集合和一條直線L，求出k個設施在L上的最佳位置，
使得所有點與最近設施的距離中的最大值為最小。我們稱以上問題為 二維直線上多個中心的設置問題。對任意的常數定值k，我們利用削減 與搜尋的方法解此問題，且此演算法的時間複雜度為O(n)。 | zh_TW |
| dc.description.abstract | In this thesis, we study the line-constrained k-center problem in the Euclidean
plane. Given a set of demand points and a line L, the problem asks for k points, called center facilities, on L, such that the maximum of the distances between the demand points to their closest center facility is minimized. For any fixed k, we propose an algorithm with running time linear to the number of demand points. | en |
| dc.description.provenance | Made available in DSpace on 2021-06-16T02:57:58Z (GMT). No. of bitstreams: 1 ntu-104-R02922077-1.pdf: 749025 bytes, checksum: 12a925eab0b1d3c1e97238c5b90740f4 (MD5) Previous issue date: 2015 | en |
| dc.description.tableofcontents | 致謝 i
摘要 ii Abstract iii Contents iv List of Figures v List of Tables vii 1 Introduction 1 2 Preliminaries 5 3 An O(n2 log n)-time algorithm for conditional k-center problem 9 4 An O(n)-time algorithm for fixed k 14 4.1 Big region . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 4.2 Solving the problem recursively . . . . . . . . . . . . . . . . . . . . . . 18 4.3 The analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 5 Concludions 30 Bibliography 31 | |
| dc.language.iso | en | |
| dc.subject | 直線上多中心設置問題 | zh_TW |
| dc.subject | 計算幾何 | zh_TW |
| dc.subject | 最小圓的覆蓋問題 | zh_TW |
| dc.subject | 削減與搜尋 | zh_TW |
| dc.subject | 設施設置問題 | zh_TW |
| dc.subject | 演算法設計 | zh_TW |
| dc.subject | 計算幾何 | zh_TW |
| dc.subject | 最小圓的覆蓋問題 | zh_TW |
| dc.subject | 削減與搜尋 | zh_TW |
| dc.subject | 直線上多中心設置問題 | zh_TW |
| dc.subject | 設施設置問題 | zh_TW |
| dc.subject | 演算法設計 | zh_TW |
| dc.subject | minimum enclosing circle | en |
| dc.subject | algorithm design | en |
| dc.subject | prune and search | en |
| dc.subject | computational geometry | en |
| dc.subject | algorithm design | en |
| dc.subject | facility location problem | en |
| dc.subject | line-constrained k-center problem | en |
| dc.subject | computational geometry | en |
| dc.subject | minimum enclosing circle | en |
| dc.subject | prune and search | en |
| dc.subject | line-constrained k-center problem | en |
| dc.subject | facility location problem | en |
| dc.title | 二維直線上多個中心的設置問題 | zh_TW |
| dc.title | Computing the line-constrained k-center Problem in the plane for small k | en |
| dc.type | Thesis | |
| dc.date.schoolyear | 103-2 | |
| dc.description.degree | 碩士 | |
| dc.contributor.oralexamcommittee | 黃耀廷(Yao-Ting Huang),王弘倫(Hung-Lung Wang) | |
| dc.subject.keyword | 計算幾何,最小圓的覆蓋問題,削減與搜尋,直線上多中心設置問題,設施設置問題,演算法設計, | zh_TW |
| dc.subject.keyword | computational geometry,minimum enclosing circle,prune and search,line-constrained k-center problem,facility location problem,algorithm design, | en |
| dc.relation.page | 34 | |
| dc.rights.note | 有償授權 | |
| dc.date.accepted | 2015-07-07 | |
| dc.contributor.author-college | 電機資訊學院 | zh_TW |
| dc.contributor.author-dept | 資訊工程學研究所 | zh_TW |
| 顯示於系所單位： | 資訊工程學系 | |
文件中的檔案：
| 檔案 | 大小 | 格式 | |
|---|---|---|---|
| ntu-104-1.pdf 未授權公開取用 | 731.47 kB | Adobe PDF |
系統中的文件，除了特別指名其著作權條款之外，均受到著作權保護，並且保留所有的權利。