Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

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?

share|improve this question
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 3 '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 3 '10 at 22:11
    
ah true. but the enumeration should work regardless. –  Suresh Venkat Dec 3 '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 3 '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 3 '10 at 22:43
show 2 more comments

2 Answers 2

up vote 16 down vote accepted

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

share|improve this answer
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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