Some Properties and Applications of the Hausdorff Distance

Abstract

Some properties of Hausdorff distance are studied. It is shown that, in every infinite-dimensional normed space, there exists a pair of closed and bounded sets such that the distance between every two points of these sets is greater than the Hausdorff distance between these sets. A relation of the obtained result to set-valued analysis is discussed.

1 Introduction

The concept of distance between sets was introduced and studied in [1] by Hausdorff. At the present time, the Hausdorff metric is widely used in both abstract and applied areas of mathematics including nonsmooth analysis (see, for example, [2, 3]), optimization theory (see, for example, [2, 4]) and calculus of variations (see, for example, [4]). Moreover, the sets approximation problem uses this concept sufficiently. Various concepts, that are widely used in optimization, such as metric regularity, covering and relative covering properties, Lipschitz and pseudo-Lipschitz properties of set-valued mappings, are also based on the Hausdorff metric (see, for example, [2]). Moreover, the concept of Hausdorff distance is closely connected with the metric fixed point and coincidence point theorems (see, for instance, the Nadler’s fixed point theorem [5] and coincidence point theorem from [6]).

The present paper is devoted to some properties of Hausdorff distance, that are closely related to optimization theory, fixed point theory and coincidence point problems.

2 Statement of the Problem

First, let us recall the definition of the Hausdorff distance. Let ($X, \rho$) be a metric space with the metric $\rho$. Denote by $B(x,r)$ a closed ball centered at $x \in X$ with the radius $r\ge 0$. Denote by $B(M,r)$ the set $\cup _{x \in M} B(x,r),$ where $M \subset X$ is a nonempty set. Let $M\subset X$, $N\subset X$ be two closed and nonempty sets. Define the Hausdorff distance between them by formula

$$\begin{aligned} h(M,N): = \inf \{r > 0 :N \subset B(M, r), M \subset B(N, r)\}, \end{aligned}$$

(1)

if there exists a number $r$ such that $N \subset B(M,r)$ and $M \subset B(N,r);$ otherwise set $h(M,N):=\infty$. It is known that on the set of closed, nonempty and bounded subsets of $X$, the Hausdorff distance is a metric.

The definition of Hausdorff distance arises the following natural question. Let $M, N$ be two closed, nonempty and bounded subsets of $X.$ Then, according to (1), for each $x \in M$ and for each $\varepsilon > 0$, there exists $y \in N$ such that $\rho \left( x,y\right) \le h(M, N) + \varepsilon$. The question is whether there exists a pair $(x, y)$ such that $x \in M, y \in N$ and $\rho \left( x,y\right) \le h(M, N)$.

Below we answer this question. At first, we prove that, under additional assumptions, known also as Bolzano–Weierstrass condition, for each $x \in M$ there exists $y \in N$ such that $\rho \left( x,y\right) \le h(M, N)$. Then, we show in Theorem 4.1 that in general, the answer is negative. More precisely, we prove that, for every infinite-dimensional normed space, there exist closed and bounded sets $M, N$ such that $\Vert x-y\Vert > h(M, N)$ for all $x \in M, y \in N$. We conclude this paper by applying these results to the investigation of Lipschitz set-valued mappings.

3 Hausdorff Distance Between Sets Satisfying Bolzano–Weierstrass Condition

Theorem 3.1

Let the sets $M$ and $N$ be closed, the set $N$ satisfy the Bolzano–Weierstrass condition, i.e., each bounded sequence in $N$ has a convergent subsequence. Then

$$\begin{aligned} \forall \; x \in M \;\exists y \in N :\rho \left( x,y\right) \le h(M, N). \end{aligned}$$

(2)

Proof

Set $r=h(M,N)$. Without loss of generality, assume that $r < \infty$. Let $x \in M$. The definition of Hausdorff distance implies that, for each natural $n$, there exists $y_n \in N$ such that $\rho \left( y_n,x\right) \le r + 1/n$. So, $\{y_n\}$ is bounded. Therefore, there exists subsequence $\{y_{n_m}\}$ and a point $y\in X$ such that $\{y_{n_m}\}$ converges to $y$. By assumption, $N$ is closed that means $y \in N$. Finally, passing to the limit as $m\rightarrow \infty$ in the inequality $\rho (y_{n_m},x)\le r+1/n_m$, we obtain $\rho \left( x,y\right) \le r$. $\square$

Obviously, every compact set satisfies the Bolzano–Weierstrass condition. Moreover, if $X=\mathbb {R}^n,$ then the Bolzano–Weierstrass theorem implies that every closed set $N\subset \mathbb {R}^n$ satisfies the Bolzano–Weierstrass condition.

Remark 3.1

The converse of this implication is not true. More precisely, in space with infinite number of elements with respect to the discrete metric condition (2) is satisfied for every closed sets $M, N$; however, there exists a bounded sequence without limit points. Indeed, let $X$ be an infinite set, $\rho$ be a discrete metric on $X$, i.e.,

$$\begin{aligned} \rho \left( x,y\right) := {\left\{ \begin{array}{ll} 0, &{}\quad x = y, \\ 1, &{}\quad x \ne y. \end{array}\right. } \end{aligned}$$

Obviously, all the subsets of $X$ are closed. Furthermore, $h(M, N) = 1$ if and only if $M \ne N.$ So, (2) is satisfied. At the same time, let $\{x_n\}$ be a sequence such that $x_n \ne x_m$ for all $n \ne m$. It is, obviously, bounded, but it has no limit points.

Remark 3.2

In the assumptions of Theorem 3.1, the inequality in (2) cannot be replaced with the equality. Moreover, in the following example, all the assumptions of Theorem 3.1 are satisfied, however,

$$\begin{aligned} \forall \,x\in M\,\,\forall \,y \in N:\, \rho (x,y) < h(M,N). \end{aligned}$$

Let $X=l_2,$

$$\begin{aligned} N=\{0\}, \,\, M=\{x_n=(x^n_1,x^n_2,\ldots ):\,\,n\in \mathbb {N},\,\, x^n_n=1-n^{-1},\,\, x^n_j=0 \,\, \forall \, j\ne n\}. \end{aligned}$$

Then $h(M,N)=1$, however, $\rho (0,x_n)=1-n^{-1}<1$ for each $n.$

Let us present one more example such that the space $X$ satisfies the Bolzano–Weierstrass condition, however,

$$\begin{aligned} \forall \,x\in M\,\,\forall \,y \in N:\, \rho (x,y) \ne h(M,N) \end{aligned}$$

and there exist points $x,u\in M,$ $y,v\in N$ such that

$$\begin{aligned} \rho (x,y)<h(M,N), \qquad \rho (u,v)>h(M,N). \end{aligned}$$

Let $X=\mathbb {R},$

$$\begin{aligned} M=\{x_n=3n: \, n=2,3,\ldots \}, \quad N=\{y_n=3n-1+n^{-1}:\, n=2,3,\ldots \}. \end{aligned}$$

Then for all $n\ge 2$ and $j\ge 2$, we have $\rho (x_n,y_j)=|3(n-j)+1-j^{-1}|\ne 1.$ However, $\rho (x_n,y_n)=1-n^{-1}<1$ for all $n,$ and $\rho (x_2,y_3)=2+3^{-1}>1.$

Let us now introduce a proposition that guaranties existence of points $x\in M$ and $y\in N$ such that the distance between them coincides with the Hausdorff distance between $M$ and $N.$

Proposition 3.1

Let the sets $M$ and $N$ be compact. Then

$$\begin{aligned} \exists \,x\in M\,\,\exists \,y \in N:\, \rho (x,y) = h(M,N). \end{aligned}$$

Proof

The definition of the Hausdorff distance implies

$$\begin{aligned} h(M,N)=\max \biggl \{ \sup \limits _{x\in M}\biggl (\inf \limits _{y\in N} \rho (x,y)\biggr ), \sup \limits _{y\in N} \biggl (\inf \limits _{x\in M} \rho (x,y)\biggr ) \biggr \}. \end{aligned}$$

Without loss of generality, assume that

$$\begin{aligned} h(M,N)=\sup \limits _{x\in M}\biggl (\inf \limits _{y\in N} \rho (x,y)\biggr ). \end{aligned}$$

Since the function $x\mapsto \inf \limits _{y\in N} \rho (x,y)$ is continuous and the set $M$ is compact, there exists a point $x\in M$ such that $\inf \limits _{y\in N} \rho (x,y)=h(M,N).$ Since the function $y\mapsto \rho (x,y)$ is continuous and the set $N$ is compact, there exists a point $y\in N$ such that $\rho (x,y)=h(M,N).$ $\square$

Note that, if the set $M$ is bounded and $h(M,N)<\infty ,$ then the set $N$ is bounded. It is obvious that in this case, the set $N$ is compact, if it satisfies the Bolzano–Weierstrass condition.

4 Hausdorff Distance Between Subsets of Normed Spaces

Let us now answer the question stated in the Introduction. First, recall the definition of the Birkhoff–James orthogonality (see [7, 8]) in normed spaces and prove some auxiliary propositions.

Remark 4.1

A vector $x$ is called orthogonal to a vector $y$ in a normed space $X,$ iff

$$\begin{aligned} \left||x\right|| \le \left||x + \alpha y\right|| \quad \forall \; \alpha . \end{aligned}$$

Denote this by $x \perp y$. A vector $x$ is called orthogonal to a subspace $L \subset X,$ iff

$$\begin{aligned} x \perp y \quad \forall \; y \in L, \end{aligned}$$

which is equivalent to the following:

$$\begin{aligned} \left||x\right|| \le \left||x + y\right|| \quad \forall \, y \in L. \end{aligned}$$

(3)

The sequence $\{e_n\}_{n=1}^\infty$ is called orthonormal in normed space $X,$ iff for all positive integer $n$

$$\begin{aligned} \left||e_n\right|| = 1, \quad e_{n+1} \perp L(e_1, \ldots , e_n), \end{aligned}$$

(4)

where $L(e_1, \ldots , e_n)$ denotes a linear hull of the vectors $e_1, \ldots , e_n$.

Lemma 4.1

Let $X$ be a finite-dimensional space and $L$ be a subspace such that $L \ne X$. Then there exists $x \in X$ such that $x \ne 0$ and $x \perp L$.

Proof

Since $L \ne X$, there exists $y \in X$ such that $y \not \in L$. Define a function $g: L \rightarrow \mathbb {R}$ by formula $g(v) = \left||v + y\right||,$ for all $v \in L$. Obviously, $g$ is continuous and

$$\begin{aligned} \exists R \ge 0: \inf \limits _{v\in B(0, R)\cap L} g(v) = \inf \limits _{v\in L} g(v). \end{aligned}$$

So, the Weierstrass theorem implies that there exists $v_0 \in L$ such that

$$\begin{aligned} g(v_0) = \inf \limits _{v\in L} g(v). \end{aligned}$$

(5)

Set $x=y + v_0$. It follows from (5) that

$$\begin{aligned} \left||x\right|| = g(v_0) \le g(v_0 + v) = \left||y + v_0 + v\right|| = \left||x + v\right|| \end{aligned}$$

for all $v \in L$. In addition, $x \ne 0$. Otherwise, $y = -v_0 \in L$ that contradicts the assumption that $y \not \in L$. $\square$

Lemma 4.2

In every infinite-dimensional normed space, there exists an orthonormal [in the sense of (4)] sequence.

Proof

Let $X$ be an infinite-dimensional normed space. We will carry out the proof by induction on $k.$ At first, let us choose a unit vector $e_1 \in X$. By the infinite-dimensionality of $X$, there exists a vector $f_2 \in X$ such that the vectors $e_1, f_2$ are linearly independent. So, $L(e_1)$ is a proper subspace of the finite-dimensional space $L(e_1, f_2)$. According to Lemma 4.1, there exists a unit vector $e_2 \in L(e_1, f_2)$ such that $e_2 \perp e_1$. Assume now that the unit vectors $e_1, \ldots , e_k$ such that $e_i \perp L(e_1, \ldots , e_{i-1})$ for all $i = \overline{2,k}$ are already constructed. Since $X$ is infinite-dimensional, there exists vector $f_{k+1}$ such that vectors $e_1, \ldots , e_k, f_{k+1}$ are linearly independent. So, $L(e_1, \ldots , e_k)$ is a proper space of the finite-dimensional space $L(e_1,\ldots , e_k, f_{k+1})$. According to Lemma 4.1, there exists a unit vector $e_{k+1} \in L(e_1, \ldots , e_k, f_{k+1})$ such that $e_{k+1} \perp L(e_1, \ldots , e_k)$. By induction, the desired orthonormal sequence exists. $\square$

Let us now present a statement that provides the negative answer to the question stated in the Introduction.

Theorem 4.1

In every infinite-dimensional normed space $X,$, there exist nonempty, bounded and closed sets $N$ and $M$ such that $\Vert x-y\Vert >h(M,N)$ for all $x\in M$ and $y\in N$.

Proof

Let us construct the sets $M$ and $N$. According to Lemma 4.2, there exists an orthonormal sequence $\{e_n\}_{n=1}^\infty$. Set $f_n=\frac{n+1}{n}e_n$. Then

$$\begin{aligned} \left||f_n - \sum \limits _{k=1}^{n-1}\alpha _k f_k\right|| \ge \left||f_n\right|| = 1 + \frac{1}{n}. \end{aligned}$$

(6)

Denote by $M$ the set of all the vectors $x\in X$ that can be represented as a sum of even amount of vectors $f_1,f_2,\ldots$. Every vector $x \in M$ can be uniquely represented in such a form because $f_1, f_2, \ldots$ are linearly independent. For all $x \in M$ denote by $m(x)$ the greatest number of the corresponding summands.

Denote by $N$ the set of all the vectors $y\in X$ that can be represented as a sum of odd amount of vectors $f_1,f_2,\ldots$. Every vector $y \in N$ can be uniquely represented in such a form because $f_1, f_2, \ldots$ are linearly independent. For every $y \in N$ denote by $n(y)$ the greatest number of the corresponding summands.

By inequality (6), we have that $M$ and $N$ are closed. Furthermore, we have

$$\begin{aligned} \left||y - x\right|| \ge 1 + \dfrac{1}{\max \{n(x), m(y)\}} > 1 \end{aligned}$$

for arbitrary $x \in M, y \in N$. Now let us estimate the Hausdorff distance $h(M, N)$. For all $x \in M$, the vector $y = x + f_k$ belongs to the set $N$ for every $k > m(x)$. Moreover, $\left||y - x\right|| = \left||f_k\right|| \rightarrow 1$ as $k \rightarrow \infty$. In a similar manner, for all $y \in N$, the vector $x = y + f_k$ belongs to the set $M$ for every $k > n(y)$. Further, $\left||x - y\right|| = \left||f_k\right|| \rightarrow 1$ when $k \rightarrow \infty$. Hence, $h(M, N) \le 1$. Thus, we constructed closed and bounded sets $M \subset X$ and $N \subset X$ such that $h(M,N) \le 1$ and $\left||x - y\right|| > 1$ for all $x \in M, y \in N$. $\square$

Theorems 3.1 and 4.1 imply the following characterization of finite-dimensional normed spaces.

Proposition 4.1

A normed space $X$ is finite-dimensional if and only if for all nonempty and closed subsets $M\subset X$ and $N\subset X$, the following relation holds:

$$\begin{aligned} \forall \; x \in M \;\exists y \in N :\rho \left( x,y\right) \le h(M, N). \end{aligned}$$

5 Comparison of Lipschitzian Set-Valued Mappings

Using the above example, let us compare two well-known definitions of Lipschitz set-valued mappings, commonly used in set-valued analysis (see, for example, [2]). Let us recall them. Let $(X, \rho _X), (Y, \rho _Y)$ be metric spaces, $\beta$ be nonnegative number. Hausdorff distance in a space of closed subsets of $Y$ we denote by $h_Y$. An analogous modification of notation we use for the balls. Namely a closed ball in a space $X$ we denote by $B_X(x,r)$. Everywhere below, we assume that a set-valued mapping $\varPhi : X \rightrightarrows Y$ is a mapping that transforms each point $x \in X$ to a closed and nonempty subset $\varPhi (x) \subset Y$.

Definition 5.1

A set-valued mapping $\varPhi : X \rightrightarrows Y$ is called $\beta$-Lipschitz in the sense of Hausdorff metric, iff

$$\begin{aligned} h_Y(\varPhi (x),\varPhi (u)) \le \beta \rho _X(x,u) \quad \forall \;x,u \in X. \end{aligned}$$

(7)

Definition 5.2

(cf [2]) A set-valued mapping $\varPhi : X \rightrightarrows Y$ is called $\beta$-Lipschitz, iff

$$\begin{aligned} \varPhi (u) \subset B_Y(\varPhi (x), \beta \rho _X(x,u)) \quad \forall \;x,u \in X. \end{aligned}$$

(8)

The result below directly follows from the definitions above.

Proposition 5.1

• 1. If set-valued mapping $\varPhi : X \rightrightarrows Y$ is $\beta$-Lipschitz, i.e., relation (8) holds, then it is $\beta$-Lipschitz in the sense of Hausdorff metric, i.e., inequality (7) holds.

• 2. If set-valued mapping $\varPhi : X \rightrightarrows Y$ is $\beta$-Lipschitz in the sense of Hausdorff metric, i.e., inequality (7) holds, then for every $\varepsilon > 0$, this mapping is $(\beta + \varepsilon )$-Lipschitz, i.e., $\varPhi (u) \subset B_Y(\varPhi (x), (\beta +\varepsilon )\rho _X(x,u))$ for all $x,u \in X.$

In Proposition 5.1.2, in general, one cannot take $\varepsilon = 0$. Consider the corresponding example.

Example 5.1

Let $Y$ be an infinite-dimensional normed space. In Theorem 4.1, it is proved that there exist closed and nonempty sets $M, N \subset Y$ such that $h_Y(M, N) \le 1$ and $\rho _Y(y, v) > 1$ for all $y \in M, v \in N$. Let $X$ be a metric space consisting of two different points $x_1, x_2$ such that $\rho _X(x_1, x_2) = 1$. Let us define $\varPhi : X \rightrightarrows Y$ as follows:

$$\begin{aligned} \varPhi (x_1):= M, \quad \varPhi (x_2):= N. \end{aligned}$$

Since $h_Y(M, N) \le 1$, $\varPhi$ is 1-Lipschitz in the sense of Hausdorff metric, i.e., inequality (7) holds. However, $\rho _Y(y, v) > 1$ for all $y \in M, v \in N$. Thus, $\varPhi$ is not $1$-Lipschitz, i.e., the relation (8) does not hold for $\beta =1$.

Example 5.1 shows that a $\beta$-Lipschitz in the sense of Hausdorff metric mapping might be not $\beta$-Lipschitz, i.e., property (7) does not imply (8).

Note that, traditionally, the results on fixed and coincidence point existence use Definition 5.1. However, sometimes it is more convenient to use Definition 5.2 instead of Definition 5.1. Let us explain this reasonings using the Nadler’s fixed point theorem.

Theorem 5.1

Assume that $X$ is a complete metric space, a set-valued mapping $\varPhi :X \rightrightarrows X$ is $\beta$-Lipschitz in the sense of Hausdorff metric for some $\beta \in [0,1[,$ i.e., relation (7) holds. Then for each $x\in X$ and for each $y\in \varPhi (x)$

$$\begin{aligned} \forall \, \varepsilon >0 \quad \exists \, \xi \in X: \quad \xi \in \varPhi (\xi ) \quad \text{ and } \quad \rho _X(x,\xi )\le \frac{\rho _X(x,y) + \varepsilon }{1-\beta }. \end{aligned}$$

This result is a version of Nadler’s fixed point theorem (see, for example, [9]). The following proposition is a direct corollary of Theorem 2 from [10].

Theorem 5.2

Assume that $X$ is a complete metric space, a set-valued mapping $\varPhi :X \rightrightarrows X$ is $\beta$-Lipschitz for some $\beta \in [0,1[,$ i.e., relation (8) holds. Then for each $x\in X$ and for each $y \in \varPhi (x)$

$$\begin{aligned} \exists \, \xi \in X: \quad \xi \in \varPhi (\xi ) \quad \text{ and } \quad \rho _X(x,\xi )\le \frac{\rho _X(x,y)}{1-\beta }. \end{aligned}$$

It is a straightforward task to ensure that Theorem 5.1 is a direct corollary of Theorem 5.2. Furthermore, if the mapping $\varPhi$ is a single-valued contraction with the contraction constant $0\le \beta <1,$ then $\varPhi$ is both $\beta$-Lipschitz and $\beta$-Lipschitz in the sense of Hausdorff metric, i.e., (7) and (8) hold. However, in this case, Theorem 5.1 states that

$$\begin{aligned} \forall \, \varepsilon >0 \quad \exists \, \xi \in X: \quad \xi =\varPhi (\xi ) \quad \text{ and } \quad \rho _X(x,\xi )\le \frac{\rho _X(x,\varPhi (x)) + \varepsilon }{1-\beta }, \end{aligned}$$

whereas Theorem 5.2 states this property with $\varepsilon =0,$ which is a stronger proposition and coincides with Banach’s contraction mappings theorem.

6 Perspectives

The described in the previous section reasonings are applicable not only to fixed point theorems but also to various results on solvability of equations and inclusion in metric spaces. For instance, in [6], the estimate of a coincidence point of single-valued mappings does not follow from the estimate of a coincidence point of set-valued mappings. However, the use of Definition 5.2 may allow to derive an estimate, that is valid in both single-valued and set-valued cases. So, the presented results can be applied to solve the following problems.

• (A) For coincidence point of two set-valued mappings, obtain exact estimates that are equivalent to the estimates of coincidence point of two single-valued mappings.

• (B) Describe and investigate the class of set-valued mappings, for which the properties (7) and (8) are equivalent.

7 Conclusions

Let us summarize the results obtained in this article.

• (A) There was considered the following question. If for two arbitrary closed and nonempty subsets of a metric space, there exists a point in each set such that the distance between these points is less or equal than the Hausdorff distance between these sets? Under assumption that one of the set satisfies the Bolzano–Weierstrass condition, the answer is positive, i.e., such points exist. In an infinite-dimensional normed space, the answer is negative, i.e., there exists a pair of closed and bounded sets such that the distance between every two points belonging to these sets is greater than the Hausdorff distance between these sets.

• (B) These two facts imply the following characterization of finite-dimensional normed spaces. A normed space is finite-dimensional if and only if for each two closed subsets of this space, there exists a point in each subset such that the distance between these points is less or equal than the Hausdorff distance between these sets.