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

  • 1
    So the full answer is $r=d\sqrt{m/(2(m+1))}$ with $m=\min(k-1,n)$?2012-07-08
  • 0
    Jung's Theorem give an upper bound for $r$. In general, one is looking for $x$ that minimizes the function $\psi(x) = \max_i ||x-p_i||^2$. At a solution we have $0 \in \partial \psi(x)$, but a nice characterization escapes me.2012-07-08
  • 0
    @copper.hat: See my comment under Mercy's answer -- I think the intended meaning of the question is to find the least $r$ that works for all points.2012-07-08
  • 0
    Hi @joriki, the other answers were deleted. When you say 'for all points, what do you mean? I think minimizing the function $\psi$ above is what the OP wants? (The minimum is attained.)2012-07-08
  • 0
    @copper.hat: Sorry, I meant "for all possible configurations of the points $p_i$".2012-07-08
  • 0
    @joriki: Thanks, you are correct, I missed that entirely. I thought the $p_i$ were part of the problem data.2012-07-08
  • 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