# Finding the largest set of points of limited diameter

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?

• 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
• 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

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