Math @ Duke

Publications [#235456] of Pankaj K. Agarwal
Papers Published
 Agarwal, PK; Overmars, M; Sharir, M, Computing Maximally Separated Sets in the Plane and Independent Sets in the Intersection Graph of Unit Disks,
Proceedings of the Annual ACMSIAM Symposium on Discrete Algorithms, vol. 15
(2004),
pp. 509518
(last updated on 2018/02/24)
Abstract: 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 diskintersection graphs: Let D be the set of unit disks centered at the points of S. The diskintersection 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 NPComplete if k is part of the input. In this paper we first present a lineartime 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.


dept@math.duke.edu
ph: 919.660.2800
fax: 919.660.2821
 
Mathematics Department
Duke University, Box 90320
Durham, NC 277080320

