# Hausdorff metric and convex hull

Let $X$ be a normed linear space and $A, B \in P(X)$. We define $\overline{co}(A) =$ the closure of the convex hull of $A$. Let $h$ denote the usual Hausdorff metric. We need to show that: $$h( \overline{co}(A),\overline{co}(B) ) \leq h(A,B)$$

Attempt:

$h( \overline{co}(A),\overline{co}(B) ) =\max \{ h^\ast(\overline{co}(A) , \overline{co}(B) ) , h^\ast(\overline{co}(B) , \overline{co}(A) ) \}$, where $h^\ast$ denotes the semi-Hausdorff distance. The problem reduces to proving: $$h^\ast(\overline{co}(A) , \overline{co}(B)) \leq h^\ast(A,B)$$

$$\sup \{ d(x, \overline{co}(B) | x \in \overline{co}(A) \} \leq \sup \{d(a,B) | a \in A \}$$

If $d(x, \overline{co}(B) \leq d(a,B)$, $\forall x \in \overline{co}(A)$ and $\forall a \in A$, then taking the supremum validates the above inequality.

We need to prove next that: $$\inf \{ \|x-y \| | y \in \overline{co}(B) \} \leq \inf \{ \| a-b \| | b \in B \}$$

Again, if $\| x – y \| \leq \| a -b \|$ holds true in general then it holds for their infimums.

Let $x = \sum\limits_{i=1}^{N} \alpha_i a_i$ where $a_i \in A$ and $\sum\limits_{i=1}^{N} \alpha_i = 1$.

Let $y = \sum\limits_{j=1}^{M} \beta_j b_j$ where $b_j \in B$ and $\sum\limits_{j=1}^{M} \beta_j = 1$.

Without loss of generality, assume $M > N$ then we let $\alpha_{N+1} = \dots = \alpha_M = 0$ and we pick any $a_{N+1} , \dots , a_M \in A$.

$\| x – y \| = \| \sum\limits_{k=1}^{M} \alpha_k a_k – \beta_k b_k \| \leq \sum\limits_{k =1}^{M} \| \alpha_k a_k – \beta_k b_k \|$ by the triangle inequality of the norm.

I am stuck here. I would like to arrive to the conclusion that the last expression is less than or equal to $\| a -b \|$, $\forall a \in A$ and $\forall b \in B$.

Any hints?

#### Solutions Collecting From Web of "Hausdorff metric and convex hull"

I don’t think you’re going to get anywhere this way- it seems as though what you’re trying to prove at the end there is stronger than what is really true!

Let $Conv(A)$ denote the convex hull of $A$, which for me will be the set of all finite convex combinations of elements of $A$. We need not worry about closures: the Hausdorff distance only sees closures, insofar as
$$h(Y,Z) = h(\overline{Y}, \overline{Z})$$
for any bounded sets $Y, Z$ (If this isn’t obvious to you, you should check it as an exercise.)

I’ll show you how to bound $d(x, Conv(B))$ for $x \in Conv(A)$. Let $x \in Conv(A)$ be fixed and let it be represented as
$$x = \sum_{i = 1}^N \alpha_i a_i$$
for elements $a_i \in A$, with $\sum_i \alpha_i = 1, \alpha_i \geq 0$. We will now choose an element of $Conv(B)$ which approximates $x$ well- to do so, we approximate the $a_i$’s with $b_i$’s in $B$. Let $\gamma > 1$ be fixed and choose $b_i \in B$ for which
$$|a_i – b_i| \leq \gamma \cdot h(A,B)$$
Now define $y = \sum_{i = 1}^N \alpha_i b_i$, and estimate using the triangle inequality:
$$|x – y| \leq \sum_{i = 1}^N \alpha_i |a_i – b_i| \leq \gamma \cdot h(A,B) \sum_{i = 1}^N \alpha_i = \gamma \cdot h(A,B)$$
We conclude that $d(x,Conv(B)) \leq \gamma \cdot h(A,B)$, and since $\gamma > 1$ was arbitrary, we may take $\gamma \to 1$ to conclude.