# Existence of the smallest bounding ball

Let $$S$$ be a nonempty bounded subset of a metric space $$(X,d)$$. The main question is simply:

Question 0. Does there exist a smallest closed ball $$B(x,r):=\{y \in X: d(x,y) \le r\}$$, with $$x \in X$$ and $$r\ge 0$$, containing $$S$$?

(As usual, smallest here is meant with partial order of set inclusion.) As it is, the question is "too general": pick $$X=\mathbf{R}\setminus \{0\}$$ with its relative topology. Then $$\{-1,1\}$$ does not have a smallest ball containing it.

This is, of course, not a new question. As we can read in the abstract here, it goes back at least to Sylvester (1857) for the case of the Euclidean space $$\mathbf{R}^2$$.

I discovered that there are a lot of works on the finite dimensional Euclidean spaces in search of efficient alghorithms to find its solution, with applications to statistics, operation research, data analysis, etc.: see the introduction on these two Wikipedia pages, namely, the smallest circle problem in dimension $$d=2$$, and the smallest bounding sphere in dimension $$d\ge 1$$.

I came across this problem reading the first page of this article of Lev. At his first definition, he writes: The limit circle of a bounded sequence of complex elements is the (unique) circle of least radius which contains within or on its boundary the limit points of the sequence. (Is its existence obvious?)

Looking at the preceeding Wikipedia page, you can find a "Proof that the minimum covering disk is unique". However, what it really proves is: "If there exists a ball with smallest radius (hence, with respect to the total order of $$\le$$) of balls containing $$S$$ then it is unique. However, it seems to miss:

1. the existence part (more explicitly, our Question 0 above);
2. why two minimal balls have necessarily the same radius.

First (incomplete) attempt to Question 0, with the additional hypothesis that $$X$$ is complete. If $$|S|=1$$ the claim is trivial, let us assume that $$|S|\ge 2$$ or equivalently $$d:=\mathrm{diam}(S)>0$$. Let $$\mathscr{B}$$ be the family of closed balls containing $$S$$, which is nonempty since $$S$$ is bounded. If $$(B(x_n,r_n): n\ge 1)$$ is a decreasing chain in $$\mathscr{B}$$ (in particular, each $$r_n \ge d$$), then the set $$F:=\bigcap_n B(x_n,r_n)$$ is closed and contains $$S$$ (however, potentially $$F$$ is not a ball). Now, we have that if $$n>k\ge 1$$ then $$d(x_n,x_k)\le r_k-r_n$$. Also, the sequence $$(r_n)$$ is lower bounded by $$d$$ and monotonically descreasing, hence $$r_\star:=\lim_nr_n$$ exists and $$(x_n)$$ is Cauchy. Since $$X$$ is complete there exists also $$x_\star:=\lim_n x_n$$. Now, fix $$\varepsilon>0$$, pick an arbitrary point $$s \in S$$, and note that $$d(s,x_\star) \le d(s,x_n)+d(x_n,x_\star)$$, which is smaller than $$r_\star+\varepsilon$$ whenever $$n$$ is sufficiently large. Therefore $$S\subseteq B(x_\star,r_\star) \subseteq \bigcap_n B(x_n,r_n)$$, hence every (countable) chain in $$\mathscr{B}$$ has a lower bound in $$\mathscr{B}$$. Hence there exists a minimal element in $$\mathscr{B}$$ by Zorn's lemma.

If $$X$$ is, additionally, a Hilbert space then the same Wikipedia's argument linked above proves that: if $$B(x_1,r_1),B(x_2,r_2)$$ are two minimal elements of $$\mathscr{B}$$, then there exists $$B(x_3,r_3) \in \mathscr{B}$$ with radius $$r_3\le \min\{r_1,r_2\}$$. Wlog $$B_3(x_3,r_3)$$ is minimal. Hence, if $$X$$ is Hilbert then the family $$\mathscr{B}_{\mathrm{minimal}}$$ of minimal balls containing $$S$$ is downward directed. How can we conclude that $$\mathscr{B}_{\mathrm{minimal}}$$ has a minimum?

Note: the answer to Question 0 (with respect to set inclusion) is "no" even if $$X$$ is complete. A counterexample is: let $$X$$ be the unit sphere on $$\mathbf{R}^2$$ and pick $$S:=\{(1,0), (-1,0)\}$$. Then there are two minimal (with respect to set inclusion) bounding spheres with intersection $$S$$, but no minimum.

Second attempt to Question 0, with the additional hypothesis that $$X$$ metric space with the Heine--Borel property. (In particular, all finite dimensional spaces, but not infinite dimensional normed vector spaces.) Pick a distinghished point $$0 \in X$$. Let us say $$S\subseteq B(0,M)$$, with $$M>0$$. Without loss of generality, $$S$$ is nonempty compact (by the Heine--Borel property). For each $$x \in X$$, the function $$S\to \mathbf{R}: s\mapsto d(s,x)$$ admits a maximum, let us say $$m_x$$, and satisfies $$d(0,x)-M \le m_x\le M+d(0,x)$$. We would like to minime $$m_x$$. If this problem has a solution $$x$$, then $$x \in B(0,3M)$$, which is compact. Hence, define the function $$f: B(0,3M) \to \mathbf{R}: x \mapsto m_x.$$ Thanks to Weiestrass' theorem, it would be sufficient to show that $$f$$ is continuous. Hence: is $$f$$ continuous? Fix $$\varepsilon>0$$ and $$x_0 \in B(0,3M)$$ and $$s_0 \in S$$ with $$\|x_0-s_0\|=m_{x_0}$$. If $$\|x-x_0\|\le \varepsilon$$ then $$m_x=\max_{s \in S}\|x-s\|\le \|x-x_0\|+\max_{s \in S}\|x_0-s\|\le \varepsilon+m_{x_0}$$ and viceversa $$m_{x_0}\le \varepsilon+m_x$$. Therefore, if $$\|x-x_0\|\le \varepsilon$$ then $$\|m_x-m_{x_0}\|\le \varepsilon$$.

Third attempt to Question 0, with the additional hypothesis that $$X$$ is Hilbert. If $$|S|=1$$ the claim is obvious. Otherwise, suppose that $$|S|\ge 2$$ and define $$R:=\{r \in \mathbf{R}: S\subseteq B_X(\eta,r) \text{ for some }\eta \in X\}.$$ Note that $$R\neq \emptyset$$ since $$S$$ is bounded. We claim that $$r_\star:=\inf R$$ is actually its minimum.

Now, for each $$n \in \omega$$, we can fix $$\eta_n \in X$$ such that $$S\subseteq B_X(\eta_n,r_n)$$ with $$r_n:=r_\star+2^{-n}$$. We claim that the sequence $$(\eta_n)$$ is Cauchy. For, fix $$n_1,n_2 \in \omega$$ with $$n_1>n_2$$. If $$B_X(\eta_{n_1},r_{n_1}) \subseteq B_X(\eta_{n_2}, r_{n_2})$$ then $$\|\eta_{n_1}-\eta_{n_2}\|\le r_{n_2}-r_{n_1}\le 2^{-n_2}$$. Otherwise, fix a vector $$v \in V:= S_X(\eta_{n_1},r_{n_1}) \cap S_X(\eta_{n_2}, r_{n_2})$$ and let $$\eta$$ be its projection on the line passing through $$\eta_{n_1}$$ and $$\eta_{n_2}$$. It follows that $$r_{n_1}^2 \le \|v-\eta\|^2 =\|v-\eta_{n_2}\|^2-\|\eta-\eta_{n_2}\|^2\le r_{n_2}^2-\frac{1}{4}\|\eta_{n_1}-\eta_{n_2}\|^2.$$ Therefore $$\|\eta_{n_1}-\eta_{n_2}\| \le \sqrt{r_{n_2}^2-r_{n_1}^2}\le \sqrt{r_{n_2}^2-r_\star^2}=\sqrt{2^{1-n_2}r_\star+2^{-2n_2}},$$ which can be made arbitrarily small if $$n_2=\min\{n_1,n_2\}$$ is sufficiently large.

Hence $$(\eta_n)$$ is convergent to some $$\eta_\star \in X$$. Then, let us show that $$S\subseteq B_X(\eta_\star, r_\star)$$. Pick $$x \in X$$ and, for each $$n \in \omega$$, fix an integer $$k_n\ge n$$ such that $$\|\eta_{k_n}-\eta_\star\|<2^{-n}$$. It follows that $$\forall n \in\omega, \quad \|x-\eta_\star\|\le \|x-\eta_{k_n}\|+\|\eta_{k_n}-\eta_\star\|\le r_\star+2^{-k_n}+2^{-n}\le r_\star+2^{-1-n}.$$ Therefore $$x \in B_X(\eta_\star, r_\star)$$, so that $$r_\star=\min R$$.

Lastly, we claim that $$\eta_\star$$ is unique. For, suppose that $$S\subseteq B_X(\eta_1, r_\star)$$ and $$S\subseteq B_X(\eta_2, r_\star)$$, for some distinct $$\eta_1,\eta_2 \in X$$. Then $$S$$ would be contained in their intersection. But this implies that $$S\subseteq B_X\left(\frac{1}{2}(\eta_1+\eta_2), r_{\star\star} \right)$$ where $$r_{\star\star}:=\sqrt{r_\star^2-\frac{1}{4}\|\eta_1-\eta_2\|^2}$$. However, this would imply that $$r_{\star\star} and $$r_{\star\star} \in R$$, contradicting that $$r_\star=\min R$$.

To conclude, my questions are:

Question 1. Am I missing something obvious? How can we conclude attempt 1? Does Question 0 have a positive answer in every Banach space?

Question 2. Is there a "good" reference on this problem for the existence of the smallest bounding ball? E.g., I didn't find the above arguments anywhere..

• In the case of Hilbert, the existence is a quick consequence of the parallelogram identity (implying a minimizing sequence of centers is Cauchy, as you said). Maybe it can be generalized to Banach with suitable norms. Feb 27, 2022 at 1:52

Let $$X$$ be the space $$\{(-1,-1),(-1,1),(1,-1),(1,1)\} \cup \{(0,x) : x \neq 0\}$$, $$d$$ the $$\ell ^ \infty$$ metric and $$S$$ the set $$\{(-1,-1),(-1,1),(1,-1),(1,1)\}$$.
The minimal closed ball cannot be centered at any element of $$S$$, because that would strictly contain the closed ball centered at $$(0,0.1)$$ with radius $$1.1$$.
Any closed ball centered at $$(0,t)$$ with minimum diameter (namely $$1+|t|$$) strictly contains the closed ball centered at $$(0,t/2)$$ with minimum diameter. So there's no smallest closed ball.
There are examples of Banach spaces $$X$$ and sets $$S$$ where there is no minimal bounding ball with respect to inclusion. For example, let $$X:=C^0([0,1])$$ with the supremum norm, and let $$S:=\{f,g\}$$ where $$f(x):=0$$ and $$g(x):=\max\{0,\min\{3x-2,1\}$$. Then every function in the intersection of the bounding balls for $$S$$ restricts to the zero function on $$[0,\frac{1}{3}]$$.
• Nope, the answer to Question 0 (note: with respect to set inclusion) is "no" even if $X$ is complete. A counterexample is: let $X$ be the unit sphere on $\mathbf{R}^2$ and pick $S:=\{(1,0), (-1,0)\}$. Then there are two minimal (with respect to set inclusion) bounding spheres with intersection $S$, but no minimum. Feb 28, 2022 at 9:23