## Small introduction to Hausdorff distance

Update: I realized that parts of this post focus on unimportant small details. Sorry for that, you may skip through those parts, hopefully at least the exercises are interesting.

The goal of this post is to introduce the notion of Hausdorff distance (a.k.a. Hausdorff metric) and give some sense of intuition and motivation for it and for how to work with it and some exercises.

Before we start, I need to mention something about my liberal use of the vague words like small, nearby, close. Recall the following two statements:

• A function $f: M \to N$ (from a metric space to another metric space) is continuous at $x$ if $d(f(x), f(y))$ is small whenever $d(x,y)$ is small.
• A function $f: M \to N$ is uniformly continuous if $d(f(x), f(y))$ is (uniformly) small whenever $d(x,y)$ is small.

Despite using the vague word small, the two statements do have precise meanings if you interpret them using epsilon delta arguments. So I am going to use those words liberally here and there, but of course some care must be taken, but as long as ambiguous statements (such as statements that might be begging the question “do you mean uniformly?”) are never used in theorems or proofs, things will be fine.

## 1. motivation and intuition

Recall this fact: Two sets $A$, $B$ are same if and only if the following two conditions holds:

• for each $a \in A$, there is $b \in B$ with $a = b$
• for each $b \in B$, there is $a \in A$ with $a = b$

Let $(M, d)$ be a metric space. In analogy to the above fact, we want to assign some topology (a pseudo-metric, in particular) to the collection of all non-empty subsets of $M$ such that two non-empty subsets $A$ and $B$ are close to each other (in that topology) if and only if there is a small number $\epsilon > 0$ such that the following two conditions holds:

• for each $a \in A$, there is $b \in B$ with $d(a, b) < \epsilon$
• for each $b \in B$, there is $a \in A$ with $d(a, b) < \epsilon$

The reason we are excluding the empty set is for minor convenience of not having to deal with cases involving $\sup \emptyset$ later. (It would be tedious if you had to divide into two cases $A = \emptyset$ and $A \ne \emptyset$ every time you had to prove something about this topology.)

Intuition for this topology is that when $A$ and $B$ are close to each other, while we may not demand that all $a \in A$ be in $B$ (and vice versa), we demand that for each $a \in A$, there be at least a nearby point $b$ that is in $B$. That is, given any point $a \in A$, we can perturb it a bit to make it a point in $B$. In other words, $A$ and $B$ look same if you look at $M$ with blurry vision.

## 2. coming up with the two definitions of the Hausdorff distance

Notice that the following four conditions are interchangeable, given two non-empty $A, B$:

• There is a small $\epsilon > 0$ such that for each $a \in A$ there is $b \in B$ with $d(a, b) < \epsilon$.
• There is a small $\epsilon > 0$ such that for each $a \in A$ there is $b \in B$ with $d(a, b) \le \epsilon$.
• $\inf \{ \epsilon > 0 : A \subset B^\epsilon\}$ is small, where $B^\epsilon := \{ x \in M : d(x, b) < \epsilon, \exists b \in B \}$.
• $\inf \{ \epsilon > 0 : A \subset B_\epsilon\}$ is small, where $B_\epsilon := \{ x \in M : d(x, b) \le \epsilon, \exists b \in B \}$.

Why would someone come up with the third and the fourth condition? If you want to define some pseudo-metric, then it is necessary for you to transition from “there is a small something such that ..” to “this quantity relating A and B is small.”, and since you have a kind of condition that it holding for some $\epsilon$ implies it holding for all $\epsilon' > \epsilon$, so it is natural for you to take the infimum of all such $\epsilon$ to implement that transition. On the other hand, there is another way to do that transition which we will get to soon, but for now let’s talk about this particular transition.

This observation that the four conditions are interchangeable motivates the following definition.

Given two non-empty subsets $A, B$ of $M$, define $d^1_H(A, B)$ to be the maximum of the following two quantities:

• $\inf \{ \epsilon > 0 : A \subset B_\epsilon\}$
• $\inf \{ \epsilon > 0 : B \subset A_\epsilon\}$

It is also equally natural to take the sum of those two quantities instead of taking the maximum, but let’s go with the maximum.

We don’t restrict to bounded subsets: for example, we might want to say that $\mathbb Z$ and $\mathbb Z + 0.01$ (as subsets of $\mathbb R$) are close to each other

Exercise. Prove that the alternative definition of $d^1_H$ using $A^\epsilon, B^\epsilon$ in place of $A_\epsilon, B_\epsilon$ is equivalent to our definition of $d^1_H$.

Now the other transition. Notice that the following conditions are interchangeable, given two non-empty subsets $A,B$.

• There is a small $\epsilon > 0$ such that for each $a \in A$ there is $b \in B$ with $d(a, b) < \epsilon$.
• There is a small $\epsilon > 0$ such that for each $a \in A$ we have $\inf_{b \in B} d(a, b) < \epsilon$.
• There is a small $\epsilon > 0$ such that $\sup_{a \in A}\inf_{b \in B} d(a, b) < \epsilon$.
• $\sup_{a \in A}\inf_{b \in B} d(a, b)$ is small.

Compare the above four conditions and you will see that the second condition is replacing the existential quantifier (in the first condition) with taking the infimum and the third condition is replacing the universal quantifier (in the second condition) with taking the supremum, and as a result, we come to the fourth condition which does not have any quantifiers.

In general, when $S$ is some non-empty subset of $\mathbb R$, all elements of $S$ being less than $\epsilon$ does not necessarily imply that $\sup S < \epsilon$, but the second condition and the third condition are nevertheless interchangeable because we are allowed to perturb $\epsilon$.

The fourth condition motivates the following definition.

Given two non-empty subsets $A, B$ of $M$, define $d^2_H(A, B)$ to be the maximum of the following two quantities:

• $\sup_{a \in A}\inf_{b \in B} d(a, b)$
• $\sup_{b \in B}\inf_{a \in A} d(a, b)$

Exercise. Prove that $d^1_H = d^2_H$.

This distance $d^1_H$ (or equivalently $d^2_H$), which we now denote by $d_H$, is the Hausdorff distance. It takes values in $[0,\infty]$.

Exercise. Given two non-empty subsets $A, B$ and two positive reals $t, \epsilon$, prove the following two properties:

• If $d_H(A, B) \le t$, then for all $a \in A$ there is $b \in B$ with $d(a, b) \le t + \epsilon$ and for all $b \in B$ there is $a \in A$ with $d(a, b) \le t + \epsilon$.
• If for all $a \in A$ there is $b \in B$ with $d(a, b) \le t$ and for all $b \in B$ there is $a \in A$ with $d(a, b) \le t$, then we have $d_H(A, B) \le t$.

Think of the two properties as characterizing the event $d_H(A, B) \le t$ (up to some epsilon of room). Use this characterization to solve the following two exercises.

Exercise. Given positive reals $s,t, \epsilon$ and non-empty subsets $A, B, C$, show that if $d_H(A, B) \le s$ and $d_H(B, C) \le t$ then $d_H(A, C) \le s + t + \epsilon$. Then use that to prove the triangle inequality: $d_H(A, C) \le d_H(A, B) + d_H(B, C)$.

Exercise. Given two non-empty subsets $A, B$, we have $d_H(A, B) = 0$ if and only if they have the same closure.

For any collection $\mathcal C$ of non-empty closed subsets of $M$ such that $d_H(A, B) < \infty$ for all $A, B \in \mathcal C$, the space $(\mathcal C, d_H)$ is a metric space.

## 3. more exercises

Exercise. Let $f_1, \dots, f_n: [0,1] \to M$ be curves in $M$ (i.e. each $f_i$ is continuous). For each $x \in [0,1]$, define $f(x) := \{f_i(x) : 1 \le i \le n \}$. Prove that $f$ is a curve too. Provide an example showing that this does not generalize to countably infinitely many curves.

Exercise. Let $f_t: [0,1] \to M$ be a curve for each $t \in [0,1]$ and assume that $(t,x) \mapsto f_t(x)$ is jointly continuous. Prove that the image $f_t([0,1])$ depends continuously on $t$, that is, when a curve dances continuously, its shadow does too.

Exercise. Let $n$ be a fixed positive integer. Let $F_n(M)$ be the collection of all non-empty finite subsets of $M$ of size $\le n$. The obvious canonical map from $M^n$ to $F_n(M)$ is a surjective continuous map. Is it a quotient map?

This entry was posted in Mathematics and tagged , . Bookmark the permalink.

### 2 Responses to Small introduction to Hausdorff distance

1. Chiboy says:

This is really a good intuition for Hausdorff distance….but I wish the exercises were solved.