Csaba Vincze (2013)

University of Debrecen

**Definition **Let A be a non-empty compact set in the space. The parallel body P(A, λ) to A with radius λ > 0 is A+λD, where D denotes the closed unit ball around the origin.

**Lemma 1.5.1 **
*The parallel bodies of a non-empty compact set A are compact. *

**Proof **The boundedness is clear. To prove that A+λD is closed choose a point p in the complement. This means that for any point a in A the distance between p and a is greater than λ. Using excercise 1.7.31 (iii) it follows that

$d(p,A):=\underset{a\in A}{\mathrm{m}\mathrm{i}\mathrm{n}}d(p,a)>\lambda $ |
(1.30) |

and the same holds for the elements of an open neighbourhood of p with a sufficiently small radius. Therefore the complement of the parallel body is open and, consequently, the parallel body is closed.

**Definition **The Hausdorff distance between two non-empty compact sets A and B in the space is defined as

$h(A,B)=\mathrm{i}\mathrm{n}\mathrm{f}\{\lambda >0|A\subset B+\lambda D\text{}and\text{}B\subset A+\lambda D\}$ |

**Remark **According to the compactness the set of positive reals satisfying

$A\subset B+\lambda D\text{}and\text{}B\subset A+\lambda D$ |

is non-empty and

$A\subset B+h(A,B)D\text{}and\text{}B\subset A+h(A,B)D$ |

**Proposition 1.5.2 **
*The Hausdorff distance is a metric on the collection of non-empty compact subsets in the space, i.e. it is positive definite *

$h(A,B)\ge 0\text{}and\text{}h(A,B)=0if\text{}and\text{}only\text{}if\text{}A=B,$ |

symmetric

$h(A,B)=h(B,A)$ |

and satisfies the triangle inequality

$h(A,C)\le h(A,B)+h(B,C).$ |

**Proof **The non-negativity of the Hausdorff distance is trivial. To prove the non-trivial part of the positive definiteness suppose that we have two different sets A and B such that there exists a point p from A which is not in B. Especially B is closed which means that its complement is open. The point p is contained in the complement of B together with an open ball centered at p
with radius λ. Therefore

$0<\lambda <d(p,B)\le h(A,B).$ |
(1.31) |

By contraposition

$h(A,B)=0\Rightarrow A\subset B.$ |

Changing the role of A and B we have that h(A,B)=0 implies that A=B. The symmetry is trivial. To prove the triangle inequality observe that

$C\subset B+h(B,C)D\subset A+h(A,B)D+h(B,C)D$ |

and thus

$C\subset A+\left(h\right(A,B)+h(B,C\left)\right)D.$ |

On the other hand

$A\subset B+h(A,B)D\subset C+h(B,C)D+h(A,B)D$ |

and thus

$A\subset C+\left(h\right(A,B)+h(B,C\left)\right)D.$ |

Therefore

$h(A,C)\le h(A,B)+h(B,C)$ |

as was to be proved. ▮

**Proposition 1.5.3 **
*(The minimax characterization) Let A and B be non-empty compact sets and *

${\lambda}_{1}:=\underset{a\in A}{\mathrm{m}\mathrm{a}\mathrm{x}}d(a,B):=\underset{a\in A}{\mathrm{m}\mathrm{a}\mathrm{x}}\left(\underset{b\in B}{\mathrm{m}\mathrm{i}\mathrm{n}}d(a,b)\right)$ |

and

${\lambda}_{2}:=\underset{b\in B}{\mathrm{m}\mathrm{a}\mathrm{x}}d(b,A):=\underset{b\in B}{\mathrm{m}\mathrm{a}\mathrm{x}}\left(\underset{a\in A}{\mathrm{m}\mathrm{i}\mathrm{n}}d(a,b)\right).$ |

Then

$h(A,B)=\mathrm{m}\mathrm{a}\mathrm{x}\left\{{\lambda}_{1},{\lambda}_{2}\right\}.$ |

**Proof **Since A is contained in the parallel body of B with radius h(A,B) it follows that

$d(a,B)\le h(A,B)$ |

for any a in A. Taking the maximum as a runs through the points of A we have that λ(1) is less or equal than h(A,B). So is λ(2) by changing the role of A and B:

$\lambda :=\mathrm{m}\mathrm{a}\mathrm{x}\left\{{\lambda}_{1},{\lambda}_{2}\right\}\le h(A,B).$ |

From the definition of λ it follows that A is a subset in B+λD and B is a subset in A+λD. Therefore

$\mathrm{m}\mathrm{a}\mathrm{x}\{{\lambda}_{1},{\lambda}_{2}\}=:\lambda \ge h(A,B).$ |

Finally λ=h(A,B) as was to be proved. ▮

**Theorem 1.5.4 **
*The space of non-empty compact subsets in the coordinate space of dimension n equipped with the Hausdorff metric is a complete metric space. *

**Proof **Let A(1), A(2), ..., A(m), ... be a Cauchy sequence with respect to the Hausdorff metric. The** first **observation is that it is uniformly bounded, i.e. there exists a solid sphere containing all the elements of the sequence. To prove the existence of such a body let ε > 0 be a given positive real number. Then there exists a natural number N such that

$h({A}_{m},{A}_{N+1})<\epsilon (m>N).$ |

This means that that A(m) is a subset of the parallel body of A(N+1) with radius ε. On the other hand we can take the maximal distance among the missing finitely many elements A(1), ..., A(N) of the sequence from A(N+1). If

$d:=\mathrm{m}\mathrm{a}\mathrm{x}\{\epsilon ,h({A}_{i},{A}_{N+1}\left)\right|i=1,\mathrm{\dots},N\}$ |

then all the elements of the sequence is contained in any solid sphere G containing the parallel body P(A(N+1),d). As a** second **step let B(k) be the closure of the union

${A}_{k}\cup {A}_{k+1}\cup \mathrm{\dots}.$ |

It is clear that B(k)'s are non-empty compact subsets in the space (compactness is clear because of Heine-Borel's theorem via uniform boundedness) and they form a decreasing nested sequence, i.e. B(k+1) is a subset in B(k). Therefore[1]

$B:={B}_{1}\cap {B}_{2}\cap \mathrm{\dots}{B}_{k}\cap \mathrm{\dots}\ne \mathrm{\varnothing}.$ |

Moreover B is compact. We prove that B(k) tends to B with respect to the Hausdorff metric. Since

${B}_{k}\supset {B}_{k+1}\supset B$ |

we have

$h({B}_{k},B)\ge h({B}_{k+1},B).$ |

This means that the sequence of the Hausdorff distances is monotone decreasing and bounded from below. Therefore it is convergent and the limit is just the infimum as k runs through the natural numbers. Suppose, in contrary, that the infimum is strictly positive. Then we can choose an element p(k) of the corresponding B(k) such that

$d({p}_{k},B)\ge r>0$ |

for any natural number k. Taking a convergent subsequence with the limit point p it follows that

$d(p,B)\ge r>0.$ |

But p must be in B because B(k) is a decreasing nested sequence of compact sets and thus p must be in B(k) for any natural number k. This is obviously a contradiction. By the definition A(k) is a subset in B(k) which implies (together with the previous convergence B(k) --> B) that A(k) is a subset of the parallel body to B with radius ε provided that k is great enough. To prove the converse relationship we use that A(k) is a Cauchy sequence. This means that if k is great enough then

$h({A}_{j},{A}_{k})<\epsilon (j\ge k>N)$ |

and, consequently,

$B\subset {B}_{k}=\text{}the\text{}closure\text{}of\text{}{\cup}_{j=k}^{\mathrm{\infty}}{A}_{j}\subset P({A}_{k},\epsilon )$ |

because the set on the right hand side is compact (especially closed) and contains each member of the union: recall the minimality property of the closure of a set.

Using that central similarities are circle-preserving transformations the property

$\lambda h(A,B)=h(\lambda A,\lambda B)(\lambda \ge 0)$ |
(1.32) |

is trivial without any extra condition. The following proposition shows that the Hausdorff distance also has a natural behavior under ''translations'' in case of non-empty compact convex sets.

**Proposition 1.5.5 **
*(Invariance under ''translations''.) If A, B and C are non-empty compact convex sets in the space then *

$h(A+C,B+C)=h(A,B).$ |

**Proof **For the sake of simplicity let

$\lambda =h(A,B)\text{}and\text{}\mathrm{\mu}=h(A+C,B+C).$ |

Since

$A\subset B+\lambda D\text{}and\text{}B\subset A+\lambda D$ |

it follows that

$A+C\subset B+C+\lambda D\text{}and\text{}B+C\subset A+C+\lambda D$ |

showing that

$h(A+C,B+C)\le h(A,B).$ |

Conversely

$A+C\subset B+C+\mu D\text{}and\text{}B+C\subset A+C+\mu D$ |

which implies by the first version of the cancellation law 1.4.3 that

$A\subset B+\mu D\text{}and\text{}B\subset A+\mu D$ |

showing that

$h(A,B)\le h(A+C,B+C).$ |

Therefore

$h(A+C,B+C)=h(A,B)$ |

as was to be proved. ▮