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 ( p , A ) : = m i n a A d ( p , a ) > λ

(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 ) = i n f { λ > 0 | A B + λ D   a n d   B A + λ D }

Remark According to the compactness the set of positive reals satisfying

A B + λ D   a n d   B A + λ D

is non-empty and

A B + h ( A , B ) D   a n d   B 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 ) 0   a n d   h ( A , B ) = 0 i f   a n d   o n l y   i f   A = B ,

symmetric

h ( A , B ) = h ( B , A )

and satisfies the triangle inequality

h ( A , C ) 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 < λ < d ( p , B ) h ( A , B ) .

(1.31)

By contraposition

h ( A , B ) = 0 A 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 B + h ( B , C ) D A + h ( A , B ) D + h ( B , C ) D

and thus

C A + ( h ( A , B ) + h ( B , C ) ) D .

On the other hand

A B + h ( A , B ) D C + h ( B , C ) D + h ( A , B ) D

and thus

A C + ( h ( A , B ) + h ( B , C ) ) D .

Therefore

h ( A , C ) 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

λ 1 : = m a x a A d ( a , B ) : = m a x a A m i n b B d ( a , b )

and

λ 2 : = m a x b B d ( b , A ) : = m a x b B m i n a A d ( a , b ) .

Then

h ( A , B ) = m a x λ 1 , λ 2 .

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

d ( a , B ) 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:

λ : = m a x λ 1 , λ 2 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

m a x { λ 1 , λ 2 } = : λ h ( A , B ) .

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 ( A m , A N + 1 ) < ε ( 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 : = m a x { ε , h ( A i , A N + 1 ) | i = 1 , , 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 A k + 1 .

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 B 2 B k .

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

B k B k + 1 B

we have

h ( B k , B ) 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 ) r > 0

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

d ( p , B ) 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 ) < ε ( j k > N )

and, consequently,

B B k =   t h e   c l o s u r e   o f   j = k A j P ( A k , ε )

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

λ h ( A , B ) = h ( λ A , λ B ) ( λ 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

λ = h ( A , B )   a n d   µ = h ( A + C , B + C ) .

Since

A B + λ D   a n d   B A + λ D

it follows that

A + C B + C + λ D   a n d   B + C A + C + λ D

showing that

h ( A + C , B + C ) h ( A , B ) .

Conversely

A + C B + C + μ D   a n d   B + C A + C + μ D

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

A B + μ D   a n d   B A + μ D

showing that

h ( A , B ) h ( A + C , B + C ) .

Therefore

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

as was to be proved. ▮