16
$\begingroup$

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?

Improve this question
$\endgroup$
7
  • 3
    $\begingroup$ 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". $\endgroup$
    – Suresh Venkat
    Dec 3, 2010 at 20:03
  • $\begingroup$ 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. $\endgroup$
    – David Eppstein
    Dec 3, 2010 at 22:11
  • $\begingroup$ ah true. but the enumeration should work regardless. $\endgroup$
    – Suresh Venkat
    Dec 3, 2010 at 22:18
  • 1
    $\begingroup$ 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. $\endgroup$
    – David Eppstein
    Dec 3, 2010 at 22:29
  • $\begingroup$ why can't I enumerate subsets, find a min enclosing ball, and calculate the cardinality inside for each ? $\endgroup$
    – Suresh Venkat
    Dec 3, 2010 at 22:43

2 Answers 2

Reset to default
15
$\begingroup$

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).

Improve this answer
$\endgroup$
9
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.