# Finding a point near other points

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

-

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)$$
So the full answer is $r=d\sqrt{m/(2(m+1))}$ with $m=\min(k-1,n)$? – joriki Jul 8 '12 at 23:22
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. – copper.hat Jul 8 '12 at 23:27
@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. – joriki Jul 8 '12 at 23:34
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.) – copper.hat Jul 8 '12 at 23:41
@copper.hat: Sorry, I meant "for all possible configurations of the points $p_i$". – joriki Jul 8 '12 at 23:48