競爭性區位設施之防禦問題

Abstract

競爭性區位設施問題是個著名並且尚未被完全解決的問題。此題目基本的型態是給定 n 個需求點，及一區位設施之集合。目標是要找到另一區位設施來搶走最多的需求點。

本論文我們加入了防禦之概念。也提出了競爭性區位設施之防禦問題。此問題的基本型態是給定 n 個需求點，找出一防禦區位設施之集合來抵抗任何之進攻區位設施之集合。我們主要專注於一對一競爭性區位設施之防禦問題也就是只需要防禦一個進攻區位設施。我們提供一O(n^2)時間以及O(n^2)空間複雜度之解法。

同時我們也討論了競爭性區位設施之防禦問題與其他計算幾何領域內的著名題目例如，Tukey 中間值及最小圓盤集合之間的關係。最後我們延伸一對一競爭性區位設施之防禦問題並證明一對k競爭性區位設施之防禦問題是NP-hard而k對一競爭性區位設施之防禦問題則是還沒有解的問題。

The competitive location problem is a well-known problem of great interest and not yet fully explored. The basic setting is: given a set of demand points and a set of existing facilities, find a new set of facilities that will attract the most demand points.

In this thesis we incorporate the idea of defense and introduce a new model called the defensive competition problem. The basic setting is: given a set of demand points, find a set of defending facilities that will defend the most demand points from any set of attacking facilities. Our main focus is on the one-to-one defensive competition problem where there is only one attacking facility to defend from. We give an O(n^2) time and O(n^2) space solution for this problem.

We also show that the one-to-one defensive competition problem is a generalization of the Tukey median problem and the smallest enclosing circle problem which are two famous problems in computational geometry. Last, we generalize the one-to-one defensive competition problem and show that the one-to-k defensive competition problem is a generalization for the (r,X_p)-medianoid problem which is NP-hard while the k-to-one defensive competition problem remains an open problem.