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

<p>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.</p>

<p>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.  </p>

CC BY-SA 2.5
2010-12-04T20:34:48.013Z
2010-12-04T22:07:59.150Z
2010-12-04T22:07:59.150Z
Sariel Har-Peled
<p>There's an $O(n^3\log n)$ time algorithm for the two-dimensional version of this problem in my paper with Jeff Erickson, "<a href="http://compgeom.cs.uiuc.edu/~jeffe/pubs/pdf/small.pdf">Iterated nearest neighbors and finding minimal polytopes</a>", 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).</p>

CC BY-SA 2.5
2010-12-03T20:57:36.477Z
2010-12-04T00:21:13.323Z
2010-12-04T00:21:13.323Z
David Eppstein
<p>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$.</p>

<p>What is the complexity of this problem?</p>

<p>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?</p>

CC BY-SA 2.5
2010-12-03T20:03:42.207Z
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
CC BY-SA 2.5
2010-12-03T22:11:34.947Z
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
CC BY-SA 2.5
2010-12-03T22:18:38.857Z
ah true. but the enumeration should work regardless.
Suresh Venkat
CC BY-SA 2.5
2010-12-03T22:29:45.957Z
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
CC BY-SA 2.5
2010-12-03T22:43:45.407Z
why can't I enumerate subsets, find a min enclosing ball, and calculate the cardinality inside for each ?
Suresh Venkat
CC BY-SA 2.5
2010-12-03T23:04:11.013Z
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
CC BY-SA 2.5
2010-12-04T22:07:24.610Z
ah I think i see.
Suresh Venkat
<ds.algorithms><reference-request><cg.comp-geom>
Finding the largest set of points of limited diameter
Marcus Ritt
# Finding the largest set of points of limited diameter

(Asked by: username_0 on 2010-12-03)

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?

**Tags:** ds.algorithms, reference-request, cg.comp-geom

> **Comments:**
> **username_1**: 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".  
> **username_2**: 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.  
> **username_1**: ah true. but the enumeration should work regardless.  
> **username_2**: 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.  
> **username_1**: why can't I enumerate subsets, find a min enclosing ball, and calculate the cardinality inside for each ?  
> **username_2**: 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.  
> **username_1**: ah I think i see.  

---

## 2 answers

### Answer by username_2 on 2010-12-03. Score: 15 | Accepted answer

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](http://compgeom.cs.uiuc.edu/~jeffe/pubs/pdf/small.pdf)", 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).


---

### Answer by username_3 on 2010-12-04. Score: 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.


---

