4
$\begingroup$

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 Answers 1

3

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

  • 0
    @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$.2011-04-15