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.

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

share|improve this question
3  
One problem that arises if you replace the sup by an inf is that the resulting distance function fails to be a pseudometric, as the triangle property fails to hold. For example, consider the sets $A=\{1\}$, $C = \{-1\}$ and $B=\{z\in\mathbb{C} | |z|=1 \}$ in $\mathbb{C}$ with the usual topology. We then have $d(A,B)=d(B,C)=0$, but $d(A,C)=2$. –  Old John Aug 17 '12 at 12:16
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. –  t.b. Aug 17 '12 at 12:18

2 Answers 2

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.

share|improve this answer
    
More specifically, the suggested distance measures the minimal distance of points $(a,b)$ with $a \in A$ and $b \in B$. The symmetrization is unnecessary, since the suggested "distance" simply is $\operatorname{dist}_{\rm new}(A,B) = \inf_{a \in A, b \in B} d(a,b)$ which is already symmetric in $A$ and $B$. –  t.b. Aug 17 '12 at 12:40
    
@t.b.: good point, I incorporated that comment into the answer. –  tomasz Aug 17 '12 at 12:47

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.

share|improve this answer

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.