Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question

1 Answer 1

up vote 3 down vote accepted

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

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.