Department of Mathematics
 Search | Help | Login | pdf version | printable version

Math @ Duke



Publications [#235456] of Pankaj K. Agarwal

Papers Published

  1. 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 ACM-SIAM Symposium on Discrete Algorithms, vol. 15 (2004), pp. 509-518
    (last updated on 2018/12/18)

    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.
ph: 919.660.2800
fax: 919.660.2821

Mathematics Department
Duke University, Box 90320
Durham, NC 27708-0320