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

Abstract

在本論文中，我們的研究對象是平面上限制在兩條直線上的 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 con­straint that the centres should lie in two lines. We study the constrained ver­sion 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 “paramet­ric search”, and then review the k­-centre problem constrained to a single line and the k-centre problems constrained to two lines of special arrange­ment, including two parallel lines and two perpendicular lines, which stimu­late 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) .