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

Published

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