5
$\begingroup$

This question already has an answer here:

From Wikipedia

The definition of the Hausdorff distance can be derived by a series of natural extensions of the distance function $d(x, y)$ in the underlying metric space $M$, as follows:[4]

  • Define a distance function between any point $x$ of $M$ and any non-empty set $Y$ of $M$ by: $$ d(x,Y)=\inf \{ d(x,y) | y \in Y \}\ . $$

  • Define a distance function between any two non-empty sets $X$ and $Y$ of $M$ by: $$ d(X,Y)=\sup \{ d(x,Y) | x \in X \}\ . $$

  • If $X$ and $Y$ are compact then $d(X,Y)$ will be finite; $d(X,X)=0$; and $d$ inherits the triangle inequality property from the distance function in $M$. As it stands, $d(X,Y)$ is not a metric because $d(X,Y)$ is not always symmetric, and $d(X,Y) = 0$ does not imply that $X = Y$ (It does imply that $X \subseteq Y$). However, we can create a metric by defining the Hausdorff distance to be: $$ d_{\mathrm H}(X,Y) = \max\{d(X,Y),d(Y,X) \} \, . $$

I was wondering why in the three steps, $\inf$ and $\sup$ are as they are? What if some or all of they are flipped between $\inf$ and $\sup$?

For example, the first step defines the distance between a point and a set by $\inf$, but the second step defines the distance between two sets by $\sup$ and the third step uses $\max$ again. Why are they not all using $\inf$ or $\min$ (or $\sup$ or $\max$, respectively), which I think would make the three steps more agreeable, since in the first step, a point can be seen as a singleton set.

Thanks and regards!

$\endgroup$

marked as duplicate by Rahul, JSchlather, Jim, Stefan Hansen, Asaf Karagila Feb 25 '13 at 8:22

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ Have you tried experimenting with your own versions to see if they satisfy the triangle inequalities? It's a nice exercise. (Do it with $M=\mathbb R^2$ to keep things concrete and easily visualized.) $\endgroup$ – user53153 Feb 24 '13 at 23:21
  • $\begingroup$ @5pm: Thanks! Is making it a metric the reason that the definition uses $\inf$ and $\sup$ in such a obscure way? $\endgroup$ – Tim Feb 24 '13 at 23:23
  • $\begingroup$ Wait, maybe I should go to bed, but isn't it $d(X,Y)=\inf_x d(x,Y)$? $\endgroup$ – Julien Feb 24 '13 at 23:31
  • 2
    $\begingroup$ $d$ measures how far the sets are from touching each other; $d_{H}$ measures how far they are from being the same. Such a sensual subject, these distances. $\endgroup$ – user53153 Feb 24 '13 at 23:48
  • 1
    $\begingroup$ @Tim The (plain) Hausdorff distance is not a good way to measure shape difference, since it is indeed affected by translation. It only works when the two sets to be compared are accurately placed "on top of each other". To account for this "placement", the notion of Gromov-Hausdorff distance is introduced. It has one more $\inf$ in it, which is taken over all possible ways to place $X$ and $Y$ together. $\endgroup$ – user53153 Feb 25 '13 at 0:05

Browse other questions tagged or ask your own question.