How to prove the uniqueness of the smallest ball containing finite points?

Question

Problem. Let $A$ be a set of finite points in Euclidean space $\mathbb R^n$. Let $B$ be the ball containing $A$ with smallest radius. Prove the uniqueness of $B$.

The natural idea is two use contradiction argument, i.e. assume that there exist two smallest balls with same radius and distinct centers. But how do I deduce a contradiction from here? I spent the whole day to think about this but no progress. Thank you for any idea!

Comment. I found a paper of Mordukhovich et. al., but they used variational analysis in their arguments, which is too strong for such a "simple" problem, I think.

Answer 1

Suppose we have two smallest (closed) balls $B_r(a)$ and $B_r(b)$ containing the points. Then consider $c = \frac{a + b}{2}$.

Let us note that for every point $e$, we see that $d(c, e) \leq \max(d(a, e), d(b, e))$. In particular, when $a \neq b$, we have $d(c, e) < \max(d(a, e), d(b, e))$.

This is a basic fact of plane geometry (since $a, b, c$ are colinear, $a, b, c, e$ are coplanar).

Edit: let us elaborate on this. Since $a, b, c, e$ are coplanar and $a \neq b$, we give coordinates to the plane and WLOG set $a = (-1, 0)$, $b = (1, 0)$, $e = (x, y)$. Then $c = (0, 0)$. Now since $-1/2 < 1/2$ we either have that $x > -1/2$ or $x < 1/2$. WLOG, suppose $x < 1/2$. Then $d(c, e)^2 = x^2 + y^2$ and $d(b, e)^2 = (1 - x)^2 + y^2 = x^2 + (1 - 2x) + y^2$. Since $x < 1/2$, we have $1 - 2x > 0$. So clearly, $d(c, e)^2 < d(b, e)^2$ and thus $d(c, e) < d(b, e)$.

It follows that for every point $x \in A$, we have $d(c, x) < r$. Therefore, we have $r' := \max\limits_{x \in A} d(c, x) < r$ since $A$ is finite. So we can form a smaller ball $B_{r'}(c)$ which contains all the points in $A$.

Answer 2

Here I propose a slightly general solution (Actually, this is an idea of my friend)

Problem. Let $A$ be a bounded set of (potentially infinite) points in a Hilbert space $V$. Then the closed ball with smallest radius containing $A$ is unique.

Let $B(a, R)$ and $B(b, R)$ be two smallest-radius closed balls containing $A$ such that $a\neq b$. The boundedness of $A$ ensures the existence of the smallest ball. Let $c=\frac{a+b}{2}$. We now want to construct a new closed ball $B(c, R')$ with $R'<R$, thus obtain a contradiction.

Since $V$ is Hilbertian, then the Parallelogram law can be applied, i.e. $$||x-c||^2=\frac{1}{2}(||x-a||^2+||x-b||^2)-||c-a||^2\leq R^2-\varepsilon^2,$$ where $x\in A\subset B(a,R)\cap B(b, R)$ and $\varepsilon:=||c-a||>0$. Thus, $$R':=\sup_{x\in A} ||x-c||\leq \sqrt{R^2-\varepsilon^2}<R.$$

Then $B(c, R')$ is a smaller ball containing $A$. We get the contradiction.

The uniqueness has been proved.

---

Further reading.

• Note that the quantity $2\sqrt{R^2-\varepsilon^2}$ is exactly the generalized diameter of the set $B(a,R)\cap B(b, R)$.
• Every Hilbert space is strictly convex, thus implies $$||x-c||<\frac{1}{2}(||x-a||+||x-b||)\leq \max(||x-a||, ||x-b||)$$ as stated by MarkSaving in above answer.
• Every Banach space satisfying the Parallelogram law is Hilbertian.
• Note that the uniqueness of the smallest ball does not hold any more if $V$ is not a strictly convex space, e.g. $\mathbb R^2$ with $\ell^\infty$-norm, even in the case that $A$ contains only two points.
• 24th July, 2021: I found a proof here

Answer 3

Let $r$ be the radius of a smallest ball containing A.

Consider the intersection $S := \bigcap_{a \in A} B_r(a)$, where $B_r(a)$ denotes the ball of radius $r$ with center $a$. Then $S$ is non-empty as it contains the center of any ball of smallest radius containing $S$. Actually for any point $s \in S$, $A \subseteq B_r(s)$. Hence we want to prove that $S$ contains only one point.

Firstly, notice that the interior of $S$ must be empty: if $x$ is in the interior of $S$, then $d(x,a) < r$ for any $a \in A$, contradicting the minimality of $r$.

Secondly, $S$ is convex (as an intersection of convex set).

Now assume $S$ contains two distinct points $p$ and $q$, by convexity it contains the segment $[p,q]$. Let $t$ be a point in the interior of $[p,q]$ (for instance its middle point). Because $t$ is not in the interior of $S$, there is point $a \in A$ such that $d(t,a) = r$. Let the segment $[p',q']$ be the intersection of $B_r(a)$ and the line $pq$. Because $p$ and $q$ are in $B_r(a)$, $[p,q]$ is contained in $[p',q']$, so $t \in [p',q']$. But then, $p'$, $q'$ and $t$ are three distinct points in the intersection of the sphere $S_r(a)$ and the line $pq$, contradiction (a sphere and a line can have at most 2 common points).