In this post, I want to discuss one of the most famous distances between subsets of \(\mathbb{R}^n\) – the Hausdorff distance. Based on that, I will also introduce some convergence analysis regarding set-valued functions. Most of the theoretical results here can be found in 1 and 2.

Distance from point to set

Let \(C\) be a nonempty subset of \(\mathbb{R}^n\) and \(x\) be any point in \(\mathbb{R}^n\), then the distance from \(x\) to \(C\) is defined to be the minimal among the distances between \(x\) and points in \(C\). Formally,

\[\mathrm{dist}(x \to C) = \min\limits_{c \in C} \|x - c\|,\]

where \(\|\cdot\|\) can be any valid norm. Geometrically, let \(x_c\) denote the projected point from \(x\) onto \(C\), then the distance from \(x\) to \(C\) is equal to the distance between \(x\) and \(x_c\).

Next, we generalize this distance to sets.

Distance from set to set

Let \(C_1\) and \(C_2\) be two nonempty subsets of \(\mathbb{R}^n\), then the distance from \(C_1\) to \(C_2\) is defined to be the supreme over all the distances from points in \(C_1\) to \(C_2\). Formally,

\[\mathrm{dist}(C_1 \to C_2) = \sup_{x \in C_1} \mathrm{dist}(x \to C_2).\]

Geometrically, if the distance from \(C_1\) to \(C_2\) is small, then this means \(C_1\) is contained in some neighbourhood of \(C_2\). More specifically, we have the following lemma.

Lemma: \(\mathrm{dist}(C_1 \to C_2) \leq \epsilon\) if and only if \(C_1 \subseteq C_2 + \mathbb{B}(0, \epsilon)\), where \(\mathbb{B}(0, \epsilon)\) is the \(\|\cdot\|\)-ball centered at \(0\) with radius \(\epsilon\).

Distance between sets

The Huasdorff-distance between \(C_1\) and \(C_2\) is then the symmetrization of the above ideas. Formally, the Huasdorff-distance between \(C_1\) and \(C_2\) is defined as

\[\mathrm{dist}(C_1, C_2) = \max\{\mathrm{dist}(C_1 \to C_2), \mathrm{dist}(C_2 \to C_1)\}.\]

The next picture is obtained from Wikipedia.

Function

Proposition:

\[\mathrm{dist}(C_1, C_2) = \sup_{\|d\| = 1} |\sigma_{C_1}(d) - \sigma_{C_2}(d)|.\]

Proof: By the previous lemma, we know that \(\mathrm{dist}(C_1, C_2) \leq \epsilon\) if and only if \(C_1 \subseteq C_2 + \mathbb{B}(0, \epsilon)\) and \(C_2 \subseteq C_2 + \mathbb{B}(0, \epsilon)\) and this means that

\[\forall \|d\| = 1,\enspace\sigma_{C_1}(d) \leq \sigma_{C_2}(d) + \epsilon \enspace \text{and} \enspace \sigma_{C_1}(d) \leq \sigma_{C_2}(d) + \epsilon.\]

Therefore, we can conclude that

\[\mathrm{dist}(C_1, C_2) = \sup_{\|d\| = 1} |\sigma_{C_1}(d) - \sigma_{C_2}(d)|.\]

Set convergence

Before introducing the concept of set convergence, we need the following definitions regarding the inner and outer limits of sets.

Definition Let \(\{C_i\}_{i = 1}^{\infty}\) be a infinite sequence of convex sets in \(\mathbb{R}^n\). The outer limit or the limes exterior of \(C_i\)’s is the set of all cluster points of all selections. Specifically,

\[\lim\mathrm{ext}_{i \to \infty} C_i = \{c \mid \exists (c_j)_{j \in J \subseteq \mathbb{N}}, \enspace \text{such that}\enspace c_j \in C_j, c_j \to c\}.\]

The inner limit or the limes interior of \(C_i\)’s is the set of limits of all convergent selections. Specifically,

\[\lim\mathrm{int}_{i \to \infty} C_i = \{c \mid \exists (c_i)_{i \in \mathbb{N}}, \enspace \text{such that}\enspace c_i \in C_i, c_i \to c\}.\]

It is clear that we always have

\[\lim\mathrm{int}_{i \to \infty} \subseteq \lim\mathrm{ext}_{i \to \infty} C_i.\]

Function

When these two sets are equal, the common set is defined to be the limit of \(C_i\)’s. Specifically,

\[C = \lim_{i \to \infty} C_i \enspace\text{iff}\enspace C = \lim\mathrm{ext}_{i \to \infty} C_i = \lim\mathrm{int}_{i \to \infty} C_i.\]

Relation with Hausdorff-distance In general, convergence with respect to Hausdorff-distance is not equivalent to set convergence as just defined. The next example will illustrate that.

Example Let \(C_i = [0, i]\) and \(C = \mathbb{R}_{\geq 0}\), then it is obviously that

\[\lim_{i \to \infty} C_i = C.\]

Hoever, the Hausdorff-distance between \(C_i\) and \(C\) is always \(\infty\).

Is there is a way to link these two convergence? The answer is yes. We just need an additional boundedness restriction.

Theorem Suppose there is a bounded set \(X \subset \mathbb{R}^n\) such that \(C_i, C \subseteq X\), then

\[\lim_{i \to \infty} C_i = C \enspace \Leftrightarrow \enspace \mathrm{dist}(C_i, C) \to 0.\]

References

  1. Hiriart-Urruty, Jean-Baptiste, and Claude Lemaréchal. Fundamentals of convex analysis. Springer Science and Business Media, 2012. 

  2. Rockafellar, R. Tyrrell, and Roger J-B. Wets. Variational analysis. Vol. 317. Springer Science & Business Media, 2009.