在設施選址問題的許多變體中，我們通常給定n個點集，需要從中選擇k個設施以最小化某個目標函數。相反，在厭惡設施選址問題中，我們需要最大化某個目標函數。在文獻中，這類旨在最大化某些多樣性度量的問題被稱為分散問題。在最大-最小k-分散問題中，我們需要最大化所選k個設施之間的最小距離。k-分散問題的應用廣泛。考慮一個具體應用，即k-分散問題可用于給定的點集處于凸位置的場景，如下所述。例如，考慮一個凸形島嶼，需要在海岸上建立一些石油儲存廠以便船只運輸。此外，這些工廠應盡可能遠離彼此，以確保任何一個工廠的事故不會影響其他工廠。我們可以將此問題建模為k-分散問題，其中工廠位于島嶼邊界上，以最大化任意兩個工廠之間的距離。我們正式定義該問題如下。

凸多邊形上的離散k-分散問題(DkConP)：給定平面上處于凸位置的n個點集S，按繞S質心的順時針順序排列形成一個凸多邊形P，目標是計算一個大小為k的子集S'?S，使得S'中任意兩點之間的最小距離最大化。觀察到，當且僅當存在k個半徑為r_max的全等圓盤，其中心放置在從凸多邊形P的n個頂點v₁, v₂, …, v_n中選擇的k個頂點（對應S'中的k個點）上時，點集S上存在k-分散問題的最優解，其值為2r_max。

對于k≥3的離散k-分散問題，即使在滿足三角不等式的情況下，已知是NP-完全的。在歐幾里得k-分散問題中，給定歐幾里得平面上的一個有限點集S，目標是從S中選出k個點，使得所選點之間的最小成對歐幾里得距離最大化。Wang和Kuo[22]證明該問題是NP-難的。隨后，Akagi等人[1]針對歐幾里得k-分散問題提出了一個運行時間為n^O(√k)的精確算法。對于給定點按直線或圓邊界順序出現的特殊情況，他們還給出了一個O(n)時間的求解算法。后來，Araki和Nakano[2]將[1]中直線情況的運行時間改進為O(log n)。Ravi等人[16]研究了圖上的最大-最小k-分散問題，并證明對于任意賦權圖，除非P=NP，否則不存在常數因子近似算法。當邊權重滿足三角不等式時，他們證明除非P=NP，否則該問題不能在多項式時間內獲得優于1/2的近似比。他們還為圖度量情況提出了一種多項式時間的1/2-近似算法。然而，同樣的1/2近似保證早已由Tamir[19]建立。

文獻中還研究了最大-最小k-分散問題的幾個變體。在一維上，考慮了一個有序區間集合上的受限分散問題，需要從每個區間中恰好選擇一個點，以在遵守給定順序的同時最大化最小成對距離；該問題允許線性時間算法[14]。對于平面上的點集，1-分散問題是平凡的，因為選擇任意單點都會導致無窮大的最小成對距離。凸位置點集的2-分散問題可以通過計算這些點凸包的直徑在O(n log n)時間內解決[17]。Horiyama等人[11]研究了平面上的最大-最小3-分散問題，并在L₁和L_∞度量下給出了O(n)時間算法，在歐幾里得(L₂)度量下給出了O(n²log n)時間算法。隨后，Kobayashi等人[12]針對給定點處于凸位置的情況，提出了最大-最小3-分散問題的O(n²)時間算法。據我們所知，之前沒有已知的、針對任意k的、凸位置點集k-分散問題的精確多項式時間算法；這一開放性問題在本文中得到了解決。Mishra等人[13]針對相同場景提出了一種運行時間為O(n⁴)的1.733-近似算法，他們稱之為凸k-分散問題。

當點任意放置在歐幾里得平面時，目前最好的近似算法仍然是Tamir[19]和Ravi等人[16]針對度量情況提出的1/2-近似算法。因此，對于設計ρ > 1/2的ρ-近似算法，該問題仍然是開放的。文獻中的其他相關結果如下。Baur和Fekete[4]研究了在多邊形內最大化所選n個點之間的直線距離的問題，他們表明除非P=NP，否則該問題無法以13/14的因子近似。Fekete和Meijer[10]研究了具有約束的離散k-分散問題，目標是在d維空間中最大化k個設施之間的平均直線距離。當k固定時，他們在線性時間內解決了該問題；當k是輸入的一部分時，他們給出了一個多項式時間近似方案。在本文會議版本[18]之后，Tkachenko和Wang[20]針對k-分散問題提出了一個O(n^7/2log n)時間算法，并為凸位置點的特殊情況k=3給出了一個O(n log n)時間算法。

本節介紹一些在討論我們DkConP問題解決方案時有用的術語和觀察。

我們用v_iv_j表示連接點v_i和v_j的線段。我們使用|·| (i) 表示線段v_iv_j的長度|v_iv_j|，(ii) 表示實數x∈R的絕對值|x|，以及 (iii) 表示任意集合S的基數|S|。令C(d_i)表示圓盤d_i的中心，D(P)表示凸多邊形P的直徑。對于給定的k，設r_ma

針對DkConP問題，我們旨在使用有界搜索樹方法開發一個固定參數算法。為此，我們首先考慮以下決策問題：

觀察到，當且僅當半徑r小于或等于半徑r_max時，決策(P, k, r)的答案是肯定的。

在本節中，我們提出了一種精確多項式時間算法，對于任意k>0，該算法在O(n⁴k²)時間內解決DkConP問題。為此，設S'?S是大小為k的點子集，對應于最優解OPT中圓盤的中心�？紤]這些k個最優中心的Delaunay三角剖分DT(S')。顯然，DT(S')的所有邊都位于S的凸包P內，同時也位于頂點恰好為S'點的凸多邊形Q內，其中Q是

在本節中，我們為DkConP問題提出了一種近似算法，當k=3時，該算法在O(log n)時間內運行，假設點按凸位置順序給定，并按該順序存儲在數據結構中�？紤]一般凸位置上的n個點集S，令P表示由這些點形成的凸多邊形。設a, b, c和d為P的四個極值點。不失一般性，令a為具有最小x坐標的極值點，b

在本文中，我們研究了凸多邊形上的k-分散問題并提出了：(i) 一個運行時間為O(2^kn²log²n)的精確固定參數算法，(ii) 一個運行時間為O(n⁴k²)的精確多項式時間算法，適用于任意k>0。出于實際目的，對于較小的k值，人們可能更喜歡(i)，對于較大的k值，則可能更喜歡(ii)，因為固定參數算法的n的多項式依賴度低于多項式時間算法。最后，我們提到，一般的歐幾里得k-分散