Ugrás a tartalomhoz

## Convex Geometry

Csaba Vincze (2013)

University of Debrecen

1.5 The Hausdorff distance

## 1.5 The Hausdorff distance

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.

Figure 3: Felix Hausdorff,1868-1942.

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\left(p,A\right):=\underset{a\in A}{\mathrm{m}\mathrm{i}\mathrm{n}}d\left(p,a\right)>\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

Remark According to the compactness the set of positive reals satisfying

is non-empty and

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

symmetric

 $h\left(A,B\right)=h\left(B,A\right)$

and satisfies the triangle inequality

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

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 (1.31)

By contraposition

 $h\left(A,B\right)=0⇒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\left(B,C\right)D\subset A+h\left(A,B\right)D+h\left(B,C\right)D$

and thus

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

On the other hand

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

and thus

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

Therefore

 $h\left(A,C\right)\le h\left(A,B\right)+h\left(B,C\right)$

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\left(a,B\right):=\underset{a\in A}{\mathrm{m}\mathrm{a}\mathrm{x}}\left(\underset{b\in B}{\mathrm{m}\mathrm{i}\mathrm{n}}d\left(a,b\right)\right)$

and

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

Then

 $h\left(A,B\right)=\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\left(a,B\right)\le h\left(A,B\right)$

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\left(A,B\right).$

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}\left\{{\lambda }_{1},{\lambda }_{2}\right\}=:\lambda \ge h\left(A,B\right).$

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

Figure 4: The minimax characterization.

Figure 5: The minimax characterization.

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\left({A}_{m},{A}_{N+1}\right)<\epsilon \left(m>N\right).$

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}\left\{\epsilon ,h\left({A}_{i},{A}_{N+1}\right)|i=1,\mathrm{\dots },N\right\}$

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\left({B}_{k},B\right)\ge h\left({B}_{k+1},B\right).$

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\left({p}_{k},B\right)\ge r>0$

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

 $d\left(p,B\right)\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\left({A}_{j},{A}_{k}\right)<\epsilon \left(j\ge k>N\right)$

and, consequently,

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\left(A,B\right)=h\left(\lambda A,\lambda B\right)\left(\lambda \ge 0\right)$ (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\left(A+C,B+C\right)=h\left(A,B\right).$

Proof For the sake of simplicity let

Since

it follows that

showing that

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

Conversely

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

showing that

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

Therefore

 $h\left(A+C,B+C\right)=h\left(A,B\right)$

as was to be proved. ▮