Let S be a set of n points in R2. Given an integer 1 ≤ k ≤ n, we wish to find a maximally separated subset I ⊆ S of size k; this is a subset for which the minimum among the (k2) 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 (k2) 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.In this paper we first present a linear-time approximation algorithm for any constant k. Next we give O(n4/3polylog(n)) exact algorithms for the cases k = 3 and k = 4. We also present a simpler nO(√k)-time algorithm (as compared with the recent algorithm in [5]) for arbitrary values of k.展开▼
机译：设 S 为 R 2 中的一组 n 个点。给定整数1≤ k ≤ n ，我们希望找到大小最大的个最大子集I ⊆ S k; 这是一个子集，其点之间的（ k 2 ）成对距离中的最小值为尽可能大。与该问题相关的决策问题是确定是否存在 I ⊆ S ，| I |。 = k ，因此 I 中所有（ k 2 ）的成对距离均为至少要说2个。这个问题也可以用磁盘相交图来表示：假设 D 是以 S点为中心的一组单位磁盘。磁盘相交图 D 的 G 图如果有非空交叉点，则通过边缘连接成对的磁盘。然后， I 是在图 G中形成独立集的磁盘中心集。如果 k 是输入的一部分。在本文中，我们首先针对任意常数 k提出一种线性时间近似算法。接下来，给出 O（n 4/3 polylog（ n ））在 k = 3和 k = 4的情况下的精确算法。 > n O （√ k ）时间算法（与[5]中的最新算法相比），任意值 k。 / I>
展开▼
