Computing maximally separated sets in the plane and independent sets in the intersection graph of unit disks
Pankaj K. Agarwal, Mark Overmars, Micha Sharir · 2004
Given an integer 1 n, we wish to find a maximally separated subset I S of size k; this is a subset for which the minimum among the pairwise distances between its points is as large as possible. The decision problem associated with this problem is to determine whether there exists I S, |I | = k, so that all pairwise distances in I are at least 2, say. 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 connects pairs of disks by an edge if they have nonempty intersection. I 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.