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
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
and satisfies the triangle inequality
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
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
On the other hand
as was to be proved. ▮
Proposition 1.5.3 (The minimax characterization) Let A and B be non-empty compact sets and
Proof Since A is contained in the parallel body of B with radius h(A,B) it follows that
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:
From the definition of λ it follows that A is a subset in B+λD and B is a subset in A+λD. Therefore
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
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
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
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
Moreover B is compact. We prove that B(k) tends to B with respect to the Hausdorff metric. Since
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
for any natural number k. Taking a convergent subsequence with the limit point p it follows that
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
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
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
Proof For the sake of simplicity let
it follows that
which implies by the first version of the cancellation law 1.4.3 that
as was to be proved. ▮