3
$\begingroup$

I have found these two definitions of Hausdorff metric.

enter image description here

Here it's written that both definitions are equivalent. I can visualize it but unable to write a mathematical proof. Can somebody help me in this?

https://en.wikipedia.org/wiki/Hausdorff_distance

$\endgroup$
8
$\begingroup$

Let $d_1$ be the first metric and $d_2$ be the second one.

Conceptual proof: Thinking of $\inf_{y \in Y} d(x,y)$ as the distance from $x$ to $Y$, $\sup_{x \in X} \inf_{y \in Y} d(x,y)$ represents the farthest point of $X$ from $Y$. Thus, $d_1(X,Y)$ gives the greatest distance a point can have from the other set. $d_2(X,Y)$ represents the smallest amount we can increase both sets to include the other. These two should clearly be equal.

.

Rigorous proof: We first show $d_1 \le d_2$. Take $\epsilon \ge 0$ so that $X \subseteq Y_\epsilon$ and $Y \subseteq X_\epsilon$. We show $d_1(X,Y) \le \epsilon$, and then it will follow $d_1(X,Y) \le d_2(X,Y)$. By symmetry, we show $\sup_{x \in X}\inf_{y \in Y}d(x,y) \le \epsilon$. So it suffices to show $\inf_{y \in Y}d(x,y) \le \epsilon$ for each $x \in X$. But for any $x \in X$, $x \in Y_\epsilon$, so there is some $y \in Y$ for which $d(x,y) \le \epsilon$, as desired.

Now we show $d_2 \le d_1$. Let $\epsilon = d_1(X,Y)$. It suffices to show $X \subseteq Y_{\epsilon+\alpha}$ and $Y \subseteq X_{\epsilon+\alpha}$ for every $\alpha > 0$ (since then $d_2 \le d_1+\alpha$ for every $\alpha \ge 0$). By symmetry, we just prove the first inclusion. Take $x_0 \in X$. Since $\sup_{x \in X}\inf_{y \in Y} d(x,y) \le d_1(X,Y) = \epsilon$, we see $\inf_{y \in Y} d(x_0,y) \le \epsilon$ and so there is some $y \in Y$ for which $d(x_0,y) \le \epsilon+\alpha$ (this is why we needed the $\alpha$: just because an $\inf$ is $\le \epsilon$, doesn't mean there is some element with distance $\le \epsilon$). Therefore, $x \in Y_{\epsilon+\alpha}$, as desired.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy