Computing Maximally Separated Sets in the Plane and Independent Sets in the Intersection Graph of Unit Disks

Journal Article

Let S be a set of n points in ℝ2. 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 (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 ⊆ S, |I| = k, so that all (k/2) 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.

Duke Authors

Cited Authors

  • Agarwal, PK; Overmars, M; Sharir, M

Published Date

  • April 15, 2004

Published In

  • Proceedings of the Annual Acm Siam Symposium on Discrete Algorithms

Volume / Issue

  • 15 /

Start / End Page

  • 509 - 518

Citation Source

  • Scopus