Computing maximally separated sets in the plane


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 (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 disk-intersection graphs: Let D be the set of unit disks centered at the points of S. The disk-intersection 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 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 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. 134-151]) for arbitrary values of k. © 2006 Society for Industrial and Applied Mathematics.

Full Text

Duke Authors

Cited Authors

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

Published Date

  • December 1, 2006

Published In

Volume / Issue

  • 36 / 3

Start / End Page

  • 815 - 834

International Standard Serial Number (ISSN)

  • 0097-5397

Digital Object Identifier (DOI)

  • 10.1137/S0097539704446591

Citation Source

  • Scopus