Please use this identifier to cite or link to this item:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/54456| Title: | 二維直線上多個中心的設置問題 Computing the line-constrained k-center Problem in the plane for small k |
| Authors: | Albert Jhih-Heng Huang 黃志恒 |
| Advisor: | 趙坤茂(Kun-Mao Chao) |
| Keyword: | 計算幾何,最小圓的覆蓋問題,削減與搜尋,直線上多中心設置問題,設施設置問題,演算法設計, computational geometry,minimum enclosing circle,prune and search,line-constrained k-center problem,facility location problem,algorithm design, |
| Publication Year : | 2015 |
| Degree: | 碩士 |
| Abstract: | 給定一個點集合和一條直線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 |
| Fulltext Rights: | 有償授權 |
| Appears in Collections: | 資訊工程學系 |
Files in This Item:
| File | Size | Format | |
|---|---|---|---|
| ntu-104-1.pdf Restricted Access | 731.47 kB | Adobe PDF |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.