# Hausdorff distance vs. distance of the boundaries

I'm tagging this question homework because I'm more interested in hints than in complete solutions. First let us give a definition.

Definition Let $X$ be a metric space. For all $F \subset X, \rho \ge 0$, let $F_\rho$ be the union of all closed $\rho$-balls centered at some point of $F$. For all compact $C, D$, call Hausdorff distance the quantity

$$d_H(C, D)=\inf(\rho \ge 0 \mid C \subset D_\rho, D \subset C_\rho).$$

Now take two simple smooth loops $\gamma_1, \gamma_2\colon[0, 2\pi]\to \mathbb{R}^2$ and denote with $D_1, D_2$ the compact subsets of $\mathbb{R}^2$ they encircle. The problem states that

$$d_H(D_1, D_2) \le \lVert \gamma_1 - \gamma_2 \rVert_{\infty}.$$

How to prove this?

I've thought about it quite a little bit. We are here asked to prove that, for every $\xi \in D_1$, there is some $\eta \in D_2$ such that $\lvert \xi - \eta \rvert \le \lVert \gamma_1-\gamma_2\rVert_{\infty}$ (the claim will follow by interchanging $D_1$ and $D_2$). In other words, it is to be shown that we can always travel from a fixed point in $D_1$ to somewhere in $D_2$ in less than $\lVert \gamma_1-\gamma_2 \rVert_{\infty}$ units of distance. But I must admit that I can't show this. Can someone lend me a hand?

-

For convex paths, you can parametrize $D_1$ and $D_2$ by continuously shrinking the paths towards their centroids; then each pair of points with the same parameters has the required relationship. I suspect this can somehow be fixed for non-convex paths.

[Edit in response to the comment:] I was being deliberately terse since you emphasized you wanted hints and not complete solutions. Now that you ask, I notice I was also being (unintentionally) somewhat unclear.

The pronoun "theirs" was ambiguous -- I meant the centroids of the paths, not of the encircled sets. Also, I should have said "linearly shrinking" instead of "continuously shrinking". So here's what I had in mind:

The centroid $C_i$ of $\gamma_i$ is

$$C_i=\frac{1}{2\pi}\int_0^{2\pi}\gamma_i(t)\mathrm{d}t\;.$$

$$K_i(\lambda,t)=\lambda\gamma_i(t) + (1-\lambda)C_i\;.$$
$$\begin{eqnarray} \lvert K_1(\lambda,t)-K_2(\lambda,t)\rvert &=& \left\lvert\left(\lambda\gamma_1(t) + (1-\lambda)C_1\right) - \left(\lambda\gamma_2(t) + (1-\lambda)C_2\right)\right\rvert \\ &=& \left\lvert\lambda(\gamma_1(t)-\gamma_2(t)) + (1-\lambda)(C_1 - C_2)\right\rvert \\ &=& \left\lvert\lambda(\gamma_1(t)-\gamma_2(t)) + (1-\lambda)\frac{1}{2\pi}\int_0^{2\pi}\left(\gamma_1(t)-\gamma_2(t)\right)\mathrm{d}t\right\rvert \\ &\le& \lambda\lvert\gamma_1(t)-\gamma_2(t)\rvert + (1-\lambda)\frac{1}{2\pi}\int_0^{2\pi}\left\lvert\gamma_1(t)-\gamma_2(t)\right\rvert\mathrm{d}t \\ &\le& \lambda\lVert\gamma_1(t)-\gamma_2(t)\rVert_\infty + (1-\lambda)\frac{1}{2\pi}\int_0^{2\pi}\lVert\gamma_1(t)-\gamma_2(t)\rVert_\infty\mathrm{d}t \\ &=& \lambda\lVert\gamma_1(t)-\gamma_2(t)\rVert_\infty + (1-\lambda)\lVert\gamma_1(t)-\gamma_2(t)\rVert_\infty \\ &=& \lVert\gamma_1(t)-\gamma_2(t)\rVert_\infty\;. \end{eqnarray}$$
Could you please explain it a bit more thoroughly? If I understand it correctly, you say that we have homotopies $K_1(\lambda, t)$ and $K_2(\lambda, t)$ s.t. $K_i(1, t)=\gamma_i(t), K_i(0, t)=\text{centroid of }D_i$. You claim that $\lvert K_1(\lambda_0, t_0) - K_2(\lambda_0, t_0) \rvert \le \lVert \gamma_1-\gamma_2 \rVert$. But... why? What control do you have on the way $K_1, K_2$ alter distances? –  Giuseppe Negro Apr 15 '11 at 11:39
@dissonance: I edited the answer in response. Now that I think about it, perhaps "centroid" isn't exactly the right term -- perhaps "average over $t$" would be better? –  joriki Apr 15 '11 at 12:34
@joriki: Great, thank you! I see that it is all about convexity of the distance function. I've thought at a reformulation of your answer that hopefully is ready for generalization to the non-convex case. Take $\xi \in D_1$. Then $\xi$ lies in a segment whose extremes lie on $\partial D_1$, say $\xi=(1-\lambda)\gamma_1(t)+\lambda \gamma_1(s)$. Call $\eta=(1-\lambda)\gamma_2(t)+\lambda \gamma_2(s) \in D_2$. Then $\lvert \xi -\eta \rvert \le (1-\lambda)\lvert \gamma_1(t)-\gamma_2(t)\rvert + \lambda \lvert \gamma_1(s)-\gamma_2(s)\rvert \le \lVert \gamma_1 - \gamma_2 \rVert$. –  Giuseppe Negro Apr 15 '11 at 16:56
@joriki: BTW (regarding the best name for $C_1, C_2$) In my humble opinion it is most intuitive to appeal to physical notation. So centroid is the best; if we have words to spare we could say "Distribute uniformly a total mass of $2\pi$ over $\gamma_1$ and call $C_1$ the center of mass" which is lenghty but (IMHO) clearer than "call $C_1$ the average over $t$ ...". –  Giuseppe Negro Apr 15 '11 at 17:03
@dissonance: Yes, I briefly thought of that reformulation, too, but I couldn't immediately see how to guarantee in the non-convex case that there will always be at least one such segment such that $\eta\in D_2$. –  joriki Apr 15 '11 at 17:31