A Couple of Simple Algorithms for $k$-Dispersion

Abstract

Given a set $P$ of $n$ points in ${\mathbf{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 (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\ge 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\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.

8 pages