2
$\begingroup$

Let $p_1, \ldots, p_k$ be $k$ points in $\mathbb{R}^n$ so that $\max_{i,j}\|p_i - p_j\| = \epsilon$ where we are employing the standard Euclidean norm.

What is the smallest $r > 0$ so that there exists some $x \in \mathbb{R}^n$ with $\|x - p_i\| \leq r$ for all $1 \leq i \leq n$?

And most importantly,

How does $r$ change with $\epsilon$, $k$ and $n$?

1 Answers 1

4

Jung's Theorem says that if $K$ is a compact set in ${\bf R}^n$ and $d=\max_{p,q\in K}\|p-q\|_2$ then there is a closed ball with radius $r\le d\sqrt{{n\over2(n+1)}}$ that contains $K$. Equality obtains for (the vertices of) the regular $n$-simplex.

As joriki suggests in the comments, the full answer is thus $r=\epsilon\sqrt{m/(2(m+1))}{\rm\ with\ }m=\min(k-1,n)$

  • 0
    @copper.hat: Well, you're right, that's how the problem is posed; I'm just suspecting that that's not how it's meant, a) because that would make it a better problem and b) because the points aren't listed in the list of dependencies in the last line.2012-07-09