二維直線上多個中心的設置問題

Computing the line-constrained k-center Problem in the plane for small k

黃志恒(Albert Jhih-Heng Huang)

指導教授 ： 趙坤茂

國立臺灣大學/電機資訊學院/資訊工程學研究所/碩士(2015年)

https://doi.org/10.6342/NTU.2015.10602

摘要

給定一個點集合和一條直線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.

並列關鍵字

computational geometry ； minimum enclosing circle ； prune and search ； line-constrained k-center problem ； facility location problem ； algorithm design

參考文獻

[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/