## Table of Contents

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 (from a metric space to another metric space) is continuous at if is small whenever is small.
- A function is uniformly continuous if is (uniformly) small whenever 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 , are same if and only if the following two conditions holds:

- for each , there is with
- for each , there is with

Let 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 such that two non-empty subsets and are close to each other (in that topology) if and only if there is a small number such that the following two conditions holds:

- for each , there is with
- for each , there is with

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

Intuition for this topology is that when and are close to each other, while we may not demand that all be in (and vice versa), we demand that for each , there be at least a nearby point that is in . That is, given any point , we can perturb it a bit to make it a point in . In other words, and look same if you look at 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 :

- There is a small such that for each there is with .
- There is a small such that for each there is with .
- is small, where .
- is small, where .

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 implies it holding for all , so it is natural for you to take the infimum of all such 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 of , define to be the maximum of the following two quantities:

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 and (as subsets of ) are close to each other

**Exercise.** Prove that the alternative definition of using in place of is equivalent to our definition of .

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

- There is a small such that for each there is with .
- There is a small such that for each we have .
- There is a small such that .
- 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 is some non-empty subset of , all elements of being less than does not necessarily imply that , but the second condition and the third condition are nevertheless interchangeable because we are allowed to perturb .

The fourth condition motivates the following definition.

Given two non-empty subsets of , define to be the maximum of the following two quantities:

**Exercise.** Prove that .

This distance (or equivalently ), which we now denote by , is the Hausdorff distance. It takes values in .

**Exercise.** Given two non-empty subsets and two positive reals , prove the following two properties:

- If , then for all there is with and for all there is with .
- If for all there is with and for all there is with , then we have .

Think of the two properties as characterizing the event (up to some epsilon of room). Use this characterization to solve the following two exercises.

**Exercise.** Given positive reals and non-empty subsets , show that if and then . Then use that to prove the triangle inequality: .

**Exercise.** Given two non-empty subsets , we have if and only if they have the same closure.

For any collection of non-empty closed subsets of such that for all , the space is a metric space.

## 3. more exercises

**Exercise.** Let be curves in (i.e. each is continuous). For each , define . Prove that is a curve too. Provide an example showing that this does not generalize to countably infinitely many curves.

**Exercise.** Let be a curve for each and assume that is jointly continuous. Prove that the image depends continuously on , that is, when a curve dances continuously, its shadow does too.

**Exercise.** Let be a fixed positive integer. Let be the collection of all non-empty finite subsets of of size . The obvious canonical map from to is a surjective continuous map. Is it a quotient map?

Pingback: Introduction to Wasserstein metric (earth mover’s distance) | Yoo Box

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