Given a set P of n points in \(\mathbb {R}^d\) , and a positive integer \(k \le 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 \ge 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 [20] to arbitrary k. In particular, it improves on previous running times for small k.
(II) Given a set P of n points in \(\mathbb {R}^3\) , and a positive integer \(k \ge 2\) , the k-dispersion problem can be solved by an algorithm running in \( {\left\{ \begin{array}{ll} O\left( n^{k-1} \log {n}\right) \text {time}, & \text {if } k \text { is even};\\ O\left( n^{k-1} \log ^2{n}\right) \text {time}, & \text {if } k \text { is odd}. \end{array}\right. } \) For \(k \ge 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.
