請用此 Handle URI 來引用此文件:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/20521
標題: | 二維兩直線上個中心的設置問題 The -Centre Problem in the Plane with Centres Constrained to Two Lines |
作者: | Jia-Ming Zheng 鄭佳銘 |
指導教授: | 趙坤茂(Kun-Mao Chao) |
關鍵字: | 計算幾何,參數化搜尋,k中心問題,受限制k中心問題,設施設置問題,最佳化問題, Computational geometry,parametric search,-centre problem,constrained -centre problem,facility location problem,optimisation problem, |
出版年 : | 2020 |
學位: | 碩士 |
摘要: | 在本論文中,我們的研究對象是平面上限制在兩條直線上的 k 中心問題。我們研究受限制版本的 k 中心問題的原因為,不受限制的 k 中心問題已被證明為 NP 困難。 我們首先介紹一項非常實用的技巧,稱作「參數化搜尋」,而後陸續介紹限制在單條直線上的 k 中心問題,以及限制在兩條特殊安排的 k 中心問題,包括兩條平行線與兩條垂直線。這些問題激發我們對任意相交直線的 k 中心問題的解法。雖然在後來發現欲解的問題缺少足夠好的性質能夠被利用來完全解決問題,我們仍透過削減少許區域,成功辨識出一個有意義的特殊狀況。最終我們得到一個 O (n log2 n) 的演算法。 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) . |
URI: | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/20521 |
DOI: | 10.6342/NTU202004168 |
全文授權: | 未授權 |
顯示於系所單位: | 資訊工程學系 |
文件中的檔案:
檔案 | 大小 | 格式 | |
---|---|---|---|
U0001-2508202018150800.pdf 目前未授權公開取用 | 592.24 kB | Adobe PDF |
系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。