《Discrete Applied Mathematics》：Algorithms for k-dispersion for points in convex position in the plane
编辑推荐：
这篇论文研究平面凸位置点集上的最大-最小k-分散问题(DkConP)，旨在从n个点中选出k个点，最大化其最小成对欧氏距离。文章提出了一个参数为k的精确固定参数算法，运行时间为O(2kn2log2n)，改进了Akagi等人(2018)的算法。对于任意k>0，文章还给出了一个精确多项式时间算法，运行时间为O(n4k2)，解决了该限制问题的复杂度悬疑。此外，当k=3且点按凸包顺序给定时，给出了一个O(log n)时间的(1/(2√2))-近似算法。
亮点
- 1.
我们首次为平面凸位置点集上的离散k-分散问题(DkConP)提供了精确的多项式时间算法。
- 2.
我们设计了一个运行时间为O(2kn2log2n)的固定参数算法，其中k是参数。
- 3.
对于任意的k>0，我们给出了一个O(n4k2)时间的精确多项式时间算法。
- 4.
当k=3时，若点按凸位置顺序给定，我们提出了一个O(log n)时间的1/(2√2)-近似算法。
介绍
在设施选址问题的许多变体中，我们通常给定n个点集，需要从中选择k个设施以最小化某个目标函数。相反，在厌恶设施选址问题中，我们需要最大化某个目标函数。在文献中，这类旨在最大化某些多样性度量的问题被称为分散问题。在最大-最小k-分散问题中，我们需要最大化所选k个设施之间的最小距离。k-分散问题的应用广泛。考虑一个具体应用，即k-分散问题可用于给定的点集处于凸位置的场景，如下所述。例如，考虑一个凸形岛屿，需要在海岸上建立一些石油储存厂以便船只运输。此外，这些工厂应尽可能远离彼此，以确保任何一个工厂的事故不会影响其他工厂。我们可以将此问题建模为k-分散问题，其中工厂位于岛屿边界上，以最大化任意两个工厂之间的距离。我们正式定义该问题如下。
凸多边形上的离散k-分散问题(DkConP)：给定平面上处于凸位置的n个点集S，按绕S质心的顺时针顺序排列形成一个凸多边形P，目标是计算一个大小为k的子集S'?S，使得S'中任意两点之间的最小距离最大化。观察到，当且仅当存在k个半径为rmax的全等圆盘，其中心放置在从凸多边形P的n个顶点v1, v2, …, vn中选择的k个顶点（对应S'中的k个点）上时，点集S上存在k-分散问题的最优解，其值为2rmax。
对于k≥3的离散k-分散问题，即使在满足三角不等式的情况下，已知是NP-完全的。在欧几里得k-分散问题中，给定欧几里得平面上的一个有限点集S，目标是从S中选出k个点，使得所选点之间的最小成对欧几里得距离最大化。Wang和Kuo[22]证明该问题是NP-难的。随后，Akagi等人[1]针对欧几里得k-分散问题提出了一个运行时间为nO(√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-分散问题，并在L1和L∞度量下给出了O(n)时间算法，在欧几里得(L2)度量下给出了O(n2log n)时间算法。随后，Kobayashi等人[12]针对给定点处于凸位置的情况，提出了最大-最小3-分散问题的O(n2)时间算法。据我们所知，之前没有已知的、针对任意k的、凸位置点集k-分散问题的精确多项式时间算法；这一开放性问题在本文中得到了解决。Mishra等人[13]针对相同场景提出了一种运行时间为O(n4)的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(n7/2log n)时间算法，并为凸位置点的特殊情况k=3给出了一个O(n log n)时间算法。
初步准备
本节介绍一些在讨论我们DkConP问题解决方案时有用的术语和观察。
我们用vivj表示连接点vi和vj的线段。我们使用|·| (i) 表示线段vivj的长度|vivj|，(ii) 表示实数x∈R的绝对值|x|，以及 (iii) 表示任意集合S的基数|S|。令C(di)表示圆盘di的中心，D(P)表示凸多边形P的直径。对于给定的k，设rma
一个精确的固定参数算法
针对DkConP问题，我们旨在使用有界搜索树方法开发一个固定参数算法。为此，我们首先考虑以下决策问题：
- •
(P, k, r)决策问题：给定一个具有n个顶点的凸多边形P，一个正整数k < n和一个半径r，是否可以在P的顶点上放置k个（不重叠的）半径为r的全等圆盘？
观察到，当且仅当半径r小于或等于半径rmax时，决策(P, k, r)的答案是肯定的。
一个精确的多项式时间算法
在本节中，我们提出了一种精确多项式时间算法，对于任意k>0，该算法在O(n4k2)时间内解决DkConP问题。为此，设S'?S是大小为k的点子集，对应于最优解OPT中圆盘的中心。考虑这些k个最优中心的Delaunay三角剖分DT(S')。显然，DT(S')的所有边都位于S的凸包P内，同时也位于顶点恰好为S'点的凸多边形Q内，其中Q是
针对k=3的亚线性时间1/(2√2)-近似算法
在本节中，我们为DkConP问题提出了一种近似算法，当k=3时，该算法在O(log n)时间内运行，假设点按凸位置顺序给定，并按该顺序存储在数据结构中。考虑一般凸位置上的n个点集S，令P表示由这些点形成的凸多边形。设a, b, c和d为P的四个极值点。不失一般性，令a为具有最小x坐标的极值点，b
结论
在本文中，我们研究了凸多边形上的k-分散问题并提出了：(i) 一个运行时间为O(2kn2log2n)的精确固定参数算法，(ii) 一个运行时间为O(n4k2)的精确多项式时间算法，适用于任意k>0。出于实际目的，对于较小的k值，人们可能更喜欢(i)，对于较大的k值，则可能更喜欢(ii)，因为固定参数算法的n的多项式依赖度低于多项式时间算法。最后，我们提到，一般的欧几里得k-分散
