16

Given points $p_1,\ldots,p_n$ in $\mathbb{R}^{d}$ and a distance $l$ find the largest subset of these points such that the Euclidian distance of no two of them exceeds $l$.

What is the complexity of this problem?

In the graph over the points which has an edge whenever the distance of two points is at most $l$, the problem is equivalent to finding a maximum clique. The converse may not hold, because not every graph can be obtained this way (an example is the star $K_{1,7}$ for $d=2$). Therefore a related question is: what is known about this class of graphs?

Suresh Venkat
  • 32,071
  • 4
  • 95
  • 271
Marcus Ritt
  • 1,450
  • 14
  • 21
  • 3
    Note that if $d$ is fixed, there's a "trivial" P-time algorithm: since such a set is enclosed in a ball of radius $l/2$, and without loss of generality the ball is minimal (i.e touches $d+1$ points), just enumerate over all subsets. You can do better, but from a complexity point of view, the problem is "easy". – Suresh Venkat Dec 03 '10 at 20:03
  • I don't think it's true that the optimal set is necessarily enclosed in a ball of radius l/2. In the plane, for instance, the three vertices of an equilateral triangle of side length l are not so enclosed. – David Eppstein Dec 03 '10 at 22:11
  • ah true. but the enumeration should work regardless. – Suresh Venkat Dec 03 '10 at 22:18
  • 1
    You can enumerate subsets inside balls, but if you make the radius l/2 then you won't find some low-diameter subsets, and if you make the radius higher than that then it's not obvious how to trim the subsets down so that they have low diameter. – David Eppstein Dec 03 '10 at 22:29
  • why can't I enumerate subsets, find a min enclosing ball, and calculate the cardinality inside for each ? – Suresh Venkat Dec 03 '10 at 22:43
  • Because, for instance, in the case of the three points forming an equilateral triangle with side length l, you can only maintain the low diameter by adding other points inside their Reuleaux triangle. If you add other points in the enclosing ball but outside the Reuleaux triangle you will increase the diameter. So either you don't enumerate that ball, and miss the triangle, or you do, and get a set of higher diameter that you have to somehow trim. – David Eppstein Dec 03 '10 at 23:04
  • ah I think i see. – Suresh Venkat Dec 04 '10 at 22:07

2 Answers2

15

There's an $O(n^3\log n)$ time algorithm for the two-dimensional version of this problem in my paper with Jeff Erickson, "Iterated nearest neighbors and finding minimal polytopes", Disc. Comp. Geom. 11:321-350, 1994. Actually the paper primarily looks at the dual problem: given the number of points in the subset, find the smallest possible diameter; but it uses the problem you describe as a subroutine. At least at the time we wrote it, we didn't know anything subexponential for higher dimensions (although if the subset has only $k$ points in it the exponential part can be made dependent on $k$ rather than $n$ using techniques in the same paper).

David Eppstein
  • 50,990
  • 3
  • 170
  • 278
9

Approximation is pretty easy if you are interested in the smallest subset with diameter at most $(1+\epsilon)l$. A linear time algorithm by using grids is by now "standard". The constant would probably be something like $2^{O(1/\epsilon^d)}$.

There is some work on finding the smallest ball containing k points, but the diameter problem is inherently harder. To see why, a good starting point is the Clarkson-Shor paper for computing the diameter in 3d.

BTW, for high dimensions, the ball problem is approximable in time exponential in $O(1/\epsilon^2)$ (or some similar noise), by using coresets (but not in the dimension!). I kind of doubt that this approach can be extended to this problem, but I might be wrong.

Suresh Venkat
  • 32,071
  • 4
  • 95
  • 271
Sariel Har-Peled
  • 9,626
  • 31
  • 53