Math @ Duke

Publications [#235486] of Pankaj K. Agarwal
Papers Published
 Agarwal, PK; Overmars, M; Sharir, M, Computing maximally separated sets in the plane,
SIAM Journal on Computing, vol. 36 no. 3
(2006),
pp. 815834, ISSN 00975397 [doi]
(last updated on 2018/03/21)
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 (2k) 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 (2k) pairwise distances in I are at least 2. 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 has as edges all pairs of disks with nonempty intersection. Any set I with the above properties 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 exact algorithms for the cases k = 3 and k = 4 that run in time O(n 4/3polylog(n)). We also present a simpler nO(√k) time exact algorithm (as compared with the recent algorithm in [J. Alber and J. Fiala, J. Algorithms, 52 (2004), pp. 134151]) for arbitrary values of k. © 2006 Society for Industrial and Applied Mathematics.


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

