Computing maximally separated sets in the plane
Let S be a set of n points in R-2. Given an integer 1 <= k <= n, we wish to find a maximally separated subset I subset of S of size k; this is a subset for which the minimum among the ((k)(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 subset of S, | I| = k, so that all ((k)(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 epsilon-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(root 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.
disk-intersection graphs independent set geometric optimization