A Couple of Simple Algorithms for k-Dispersion
Ke Chen and Adrian Dumitrescu
给定𝐑^d空间中的n个点组成的集合P，以及正整数k ≤ n，k-分散问题是从给定点中选择k个点，使得它们之间的最小点间距离（在欧几里得距离下）最大化。我们展示了以下结果：（I）给定平面中的n个点集合P和正整数k ≥ 2，k-分散问题可以通过运行时间为O(n^k-1logn)的算法求解。这将Horiyama、Nakano、Saitoh、Suetsugu、Suzuki、Uehara、Uno和Wasa（2021）针对k=3的早期结果推广到任意k。特别地，对于较小的k，它改进了之前的运行时间。（II）给定𝐑^3空间中的n个点集合P和正整数k ≥ 2，如果k是偶数，k-分散问题可以通过运行时间为O(n^k-1logn)的算法求解；如果k是奇数，则运行时间为O(n^k-1log^2n)。对于k ≥ 4，此前没有已知的运行时间为o(n^k)的组合算法可以解决此问题。（III）设P是在[0,1]^2中均匀分布的n个随机点组成的集合。那么在适当条件下，可以在O(n)时间内以高概率计算k-分散的0.99近似解。
Given a set P of n points in 𝐑^d, and a positive integer k ≤ 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 ≥ 2, the k-dispersion problem can be solved by an algorithm running in O(n^k-1logn) time. This extends an earlier result for k=3, due to Horiyama, Nakano, Saitoh, Suet...
