Computing Maximally Separated Sets in the Plane
Pankaj K. Agarwal, Mark Overmars, Micha Sharir · SIAM Journal on Computing · 2006
Let S be a set of n points in $\reals^2$. Given an integer $1 \le k \le n$, we wish to find a maximally separated subset $I \subseteq S$ of size k; this is a subset for which the minimum among the ${k\choose 2}$ pairwise distances between its points is as large as possible. The decision problem associated with this problem is to determine whether there exists $I\subseteq S$, $|I|=k$, so that all ${k\choose 2}$ pairwise distances in I are at least 2. This problem can also be formulated in terms of disk‐intersection graphs: Let D be the set of unit disks centered at the points of S. The disk‐intersection graph G of D has as edges all pairs of disks with nonempty intersection. Any set I with the above properties is then the set of centers of disks that form an independent set in the graph G. This problem is known to be NP‐complete if k is part of the input. In this paper we first present a linear‐time $\eps$‐approximation algorithm for any constant k. Next we give exact algorithms for the cases $k=3$ and $k=4$ that run in time $O(n^{4/3}\polylog(n))$. We also present a simpler $n^{O(\sqrt{k})}$‐time exact algorithm (as compared with the recent algorithm in [J. Alber and J. Fiala, J. Algorithms, 52 (2004), pp. 134–151]) for arbitrary values of k.