Given a set $P$ of $n$ points in $\mathbf{R}^d$, and a positive integer $k \leq n$, the $k$-dispersion problem is that of selecting $k$ of the given points so that the minimum inter-point distance among them is maximized (under Euclidean distances). Among others, we show the following: (I) Given a set $P$ of $n$ points in the plane, and a positive integer $k \geq 2$, the $k$-dispersion problem can be solved by an algorithm running in $O\left(n^{k-1} \log{n}\right)$ time. This extends an earlier result for $k=3$, due to Horiyama, Nakano, Saitoh, Suetsugu, Suzuki, Uehara, Uno, and Wasa (2021) to arbitrary $k$. In particular, it improves on previous running times for small $k$. (II) Given a set $P$ of $n$ points in $\mathbf{R}^3$, and a positive integer $k \geq 2$, the $k$-dispersion problem can be solved by an algorithm running in $O\left(n^{k-1} \log{n}\right)$ time, if $k$ is even; and $O\left(n^{k-1} \log^2{n}\right)$ time, if $k$ is odd. For $k \geq 4$, no combinatorial algorithm running in $o(n^k)$ time was known for this problem. (III) Let $P$ be a set of $n$ random points uniformly distributed in $[0,1]^2$. Then under suitable conditions, a $0.99$-approximation for $k$-dispersion can be computed in $O(n)$ time with high probability.

翻译：给定$\mathbf{R}^d$空间中包含$n$个点的集合$P$，以及满足$k \leq n$的正整数$k$，$k$-分散问题旨在从给定点集中选择$k$个点，使得这些点之间的最小欧几里得距离最大化。本文主要贡献如下：（I）对于平面上包含$n$个点的集合$P$及满足$k \geq 2$的正整数$k$，$k$-分散问题可通过时间复杂度为$O\left(n^{k-1} \log{n}\right)$的算法求解。该结果将Horiyama、Nakano、Saitoh、Suetsugu、Suzuki、Uehara、Uno和Wasa（2021）针对$k=3$的结论推广至任意$k$值，尤其在小$k$情况下改进了先前的算法时间复杂度。（II）对于$\mathbf{R}^3$空间中包含$n$个点的集合$P$及满足$k \geq 2$的正整数$k$，当$k$为偶数时，$k$-分散问题可通过$O\left(n^{k-1} \log{n}\right)$时间复杂度的算法求解；当$k$为奇数时，算法时间复杂度为$O\left(n^{k-1} \log^2{n}\right)$。对于$k \geq 4$的情况，此前尚未发现时间复杂度低于$o(n^k)$的组合算法。（III）设$P$为在$[0,1]^2$区域内均匀随机分布的$n$个点集，则在适当条件下，能以高概率在$O(n)$时间内计算出$k$-分散问题的$0.99$近似解。