Hausdorff distance vs. distance of the boundaries

846 Views Asked by At

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).$$

(Wikipedia on Hausdorff distance).

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?

1

There are 1 best solutions below

5
On BEST ANSWER

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\;.$$

Define (adopting your notation)

$$K_i(\lambda,t)=\lambda\gamma_i(t) + (1-\lambda)C_i\;.$$

Then

$$ \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} $$