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. Pingback: Introduction to Wasserstein metric (earth mover’s distance) | Yoo Box

  2. Chiboy says:

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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s