7
$\begingroup$

$\newcommand{\dist}{\mathrm{dist}\,}$ Let $M$ be a metric space and $\emptyset\neq A,B\subset M$ bounded closed subsets. The Hausdorff distance is defined as $h(A,B)=\max\{\dist(A,B),\dist(B,A)\},$ where $\dist(A,B)=\sup_{x\in A}\inf_{y\in B}d(x,y).$

Why do we define $\dist(A,B)$ in this way? Is't it possible to replace the supremum by the infimum in the definition of $\dist\!$, that is, define $\dist_{\mathrm{new}}(A,B)=\inf_{x\in A}\inf_{y\in B}d(x,y).$

What is the impact of this 'new' definition on the 'Hausdorff distance' given by $h_{\mathrm{new}}(A,B)=\max\{\dist_{\mathrm{new}}(A,B),\dist_{\mathrm{new}}(B,A)\}?$

  • 3
    Another problem (related to @Old John's observation) is that your suggested distance is zero already if $A$ and $B$ share a point while the Hausdorff distance is a genuine distance function.2012-08-17

2 Answers 2

6

Here's my intuition on how you could have invented the Hausdorff distance. Hopefully it helps.

You want a metric that tells you how far two compact sets are from being the same. And since these sets happen to be subsets of a metric space, you ought to define your metric in terms of the distances between the points of $A$ and $B$.

Suppose $A\ne B$. Then either there is a point in $A$ that is not in $B$, or there is a point in $B$ that is not in $A$ (or both).

Let's say there is an $a\in A$ with $a\not\in B$. How far is $a$ from being in $B$? Well, the least you have to move $a$ to get it into $B$ is the distance to the closest point in $B$, which is $\inf_{b\in B} d(a,b)$. So that's the distance from $a$ to $B$, which we might as well call $d(a,B)$. Observe that if $a\in B$ then $d(a,B)=0$, and because $B$ is compact, if $a\not\in B$ then $d(a,B)>0$.

Now there are lots of points $a\in A$, some of which may be in $B$, and some may not. As long as there exists any $a\not\in B$, that is, any $a$ such that $d(a,B)>0$, we want to know about it. So we ought to take the supremum: $d_1(A,B)=\sup_{a\in A}d(a,B)$. This also means that every point in $A$ is at most $d_1(A,B)$ away from $B$.

Finally, $d_1(A,B)$ only tells us if there is a point in $A$ that is far from $B$. We want the Hausdorff distance $d_H(A,B)$ to be large if either there is a point in $A$ far from $B$, or there is a point in $B$ far from $A$. So we define it to be the maximum of both $d_1(A,B)$ and $d_1(B,A)$. And we're done.

5

The intuition behind Hausdorff distance is to measure “how similar” two sets are in the metric sense. If two sets are in small Hausdorff distance, they are supposed to “look” almost the same.

For example, if $A$ was some arbitrary compact set on the plane and $B$ was its countable dense subset, then the Hausdorff distance between them would be zero, which is to be expected, since they “look” pretty much the same, if you don't look too close. You might want to take a look at the picture in the Wikipedia article, I found that it is quite helpful to intuitively see how the distance works.

Furthermore, if we take a locally compact metric space $X$, Hausdorff distance turns the set $\mathcal K(X)$ of non-empty compact subsets of $X$ into a well-behaved metric space (into which $X$ naturally isometrically embeds). Your definition could not do such a thing, because it would fail pretty much all axioms of metric except nonnegativity and symmetry.

That's not to say that what you defined does not make sense (though, as suggested by t.b., the symmetrisation is unnecessary, because $\inf_{x\in A}\inf_{y\in B}d(x,y)=\inf_{(x,y)\in A\times B} d(x,y)=\inf_{y\in B}\inf_{x\in A}d(x,y)$). It does measure how “close” sets are to one another. It's just that it's not what Hausdorff distance is about.

  • 0
    @t.b.: good point, I incorporated that comment into the answer.2012-08-17