A couple of simple algorithms for k-dispersion

Abstract Given a set P of n points in $$\mathbb {R}^d$$ R d , and a positive integer $$k \le n$$ 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: Given a set P of n points in the plane, and a positive integer $$k \ge 2$$ k ≥ 2 , the k -dispersion problem can be solved by an algorithm running in $$O\left( n^{k-1} \log {n}\right) $$ O n k - 1 log n time. This extends an earlier result for $$k=3$$ 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 . Given a set P of n points in $$\mathbb {R}^3$$ R 3 , and a positive integer $$k \ge 2$$ k ≥ 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. } $$ O n k - 1 log n time , if k is even ; O