請用此 Handle URI 來引用此文件：
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/54456| 標題: | 二維直線上多個中心的設置問題 Computing the line-constrained k-center Problem in the plane for small k |
| 作者: | Albert Jhih-Heng Huang 黃志恒 |
| 指導教授: | 趙坤茂(Kun-Mao Chao) |
| 關鍵字: | 計算幾何,最小圓的覆蓋問題,削減與搜尋,直線上多中心設置問題,設施設置問題,演算法設計, computational geometry,minimum enclosing circle,prune and search,line-constrained k-center problem,facility location problem,algorithm design, |
| 出版年 : | 2015 |
| 學位: | 碩士 |
| 摘要: | 給定一個點集合和一條直線L，求出k個設施在L上的最佳位置，
使得所有點與最近設施的距離中的最大值為最小。我們稱以上問題為 二維直線上多個中心的設置問題。對任意的常數定值k，我們利用削減 與搜尋的方法解此問題，且此演算法的時間複雜度為O(n)。 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. |
| URI: | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/54456 |
| 全文授權: | 有償授權 |
| 顯示於系所單位： | 資訊工程學系 |
文件中的檔案：
| 檔案 | 大小 | 格式 | |
|---|---|---|---|
| ntu-104-1.pdf 目前未授權公開取用 | 731.47 kB | Adobe PDF |
系統中的文件，除了特別指名其著作權條款之外，均受到著作權保護，並且保留所有的權利。