Beiträge zur Algebra und Geometrie Contributions to Algebra and Geometry Volume 41 (2000), No. 1, 107-114.

On the Symmetric Difference Metric for Convex Bodies

H. Groemer

Department of Mathematics, The University of Arizona Tucson, AZ 85721, U.S.A. e-mail: groemer@math.arizona.edu

Abstract. Explicit inequalities are proved that relate the Hausdorff metric for convex bodies with the symmetric difference metric and a corresponding surface area deviation measure.

Let K^{n} denote the class of all nonempty compact convex subsets of the euclidean ndimensional space R^{n}. The members of K^{n} will be referred to as convex bodies or, more specifically, as convex bodies in R^{n}. One of the indispensable tools in the theory of convex sets is the concept of a ‘distance’ or a ‘deviation’ between two convex bodies. In this note we concern ourselves with the following three notions of this kind.

(a) The Hausdorff Metric. To define it denote for any M ∈ K^{n} its support function by h_{M}(u), that is, h_{M}(u) = sup{u · x : x ∈ M}, where the dot denotes the inner product. Then the Hausdorff distance between two bodies K, L ∈ K^{n} is defined by

δ(K, L) = sup{|h_{L}(u) − h_{K}(u)| : u ∈ S^{n−1}},

where S^{n−1} denotes the unit sphere in R^{n} (centered at the origin of R^{n}). This is the most often used distance concept for convex bodies.

(b) The symmetric difference metric. This is defined by assigning to K, L ∈ K^{n} the distance

Δ_{v}(K, L) = v(K ∪ L) − v(K ∩ L),

where v denotes the volume in R^{n}. Equivalently, it can be written in the occasionally more convenient form Δ_{v}(K, L) = (v(K) − v(K ∩ L)) + (v(L) − v(K ∩ L)).

(c) The symmetric surface area deviation. This is defined similarly as the symmetric difference metric but with the volume v replaced by the surface area s. Thus, we write

Δ_{s}(K, L) = s(K ∪ L) − s(K ∩ L),

which can also be expressed as Δ_{s}(K, L) = (s(K)−s(K ∩L))+(s(L)−s(K ∩L)). Δ_{s} does not, in general, define a metric since it does not satisfy the triangle inequality. Nevertheless it is an interesting deviation measure. See Florian [2] for further comments regarding this and closely related deviation measures.

There exist many other metrics and deviation measures that have been investigated. In particular, we mention the L_{p}-metric. For any p ≥ 1 it is defined by

δ_{p}(K, L) = (∫_{S^{n−1}} |h_{L}(u) − h_{K}(u)|^{p}dσ(u))^{1/p} ,

where σ(u) refers to the surface area on S^{n−1}. Note that if n = 2 and K ⊂ L then δ_{1}(K, L) = Δ_{s}(K, L). For further discussions of metrics and deviation measures on K^{n} see Gruber [3]. It is often necessary or desirable to make a transition from one metric to another. For this purpose one needs conversion formulas which, in their most practical forms, can be expressed as inequalities between these metrics. For example, Vitale [6] proved inequalities of this kind relating the L_{p}-metric to the Hausdorff metric. It is the aim of the present article to establish similar relations for the Hausdorff metric on the one hand, and the symmetric difference metric and surface area deviation on the other hand. In this connection we also mention the work of Shephard and Webster [5] where the topological equivalence between the Hausdorff metric and the symmetric difference metric is proved. Our objective, however, is to establish explicit inequalities.

The following theorem contains our principal result. In this theorem κ_{n} denotes the volume, and σ_{n} the surface area of the n-dimensional unit ball; diam X denotes the diameter and int X the interior of any X ⊂ R^{n}.

Theorem. Assume that K, L ∈ K^{n}, and let D = max {diam K, diam L}. Furthermore, if int (K ∩ L) ≠ ∅ let r denote the inradius of K ∩ L. Then the following statements hold.

(i) For all n ≥ 2

Δ_{v}(K, L) ≤ c_{1}δ(K, L),  (1)

where c_{1} = \frac{2κ_{n}}{2^{1/n}−1} (\frac{D}{2} )^{n−1}.

(ii) If int (K ∩ L) ≠ ∅, then for all n ≥ 2

δ(K, L) ≤ c_{2}Δ_{v}(K, L)^{1/n}  (2)

with c_{2} = (\frac{n}{κ_{n−1}} )^{1/n} (\frac{D}{r} )^{(n−1)/n}.

(iii) If int (K ∩ L) ≠ ∅, then for all n ≥ 2

Δ_{s}(K, L) ≤ c_{3}δ(K, L),  (3)

where c_{3} = σ_{n} (\frac{D}{2} )^{n−2} (\frac{5D}{2r} )^{n−1}. (If n = 2 one may choose c_{3} = 4πD/r.)

(iv) If int (K ∩ L) ≠ ∅, then for all n ≥ 3

δ(K, L) ≤ c_{4}Δ_{s}(K, L)^{1/(n−1)}  (4)

with c_{4} = (\frac{\sqrt{5}+1)}{2κ_{n−1}})^{1/(n−1)} (\frac{D}{r} )^{(n−2)/(n−1)}, and if K ∩ L ≠ ∅ and n = 2, then

δ(K, L) ≤ c_{5}Δ_{s}(K, L)^{1/2},  (5)

where c_{5} = (\frac{\sqrt{2}+1}{2}D)^{1/2}.

These five inequalities cannot be improved in the sense that the exponents of Δ_{v}(K, L) in (2) and Δ_{s}(K, L) in (4) and (5) cannot be replaced by any larger numbers (for any choice of c_{2} , c_{4} , c_{5} depending on n, D, and r only). Similarly, in (1) and (3) δ(K, L) cannot be replaced by any δ(K, L)^{α} with α > 1 (for any appropriate choice of the coefficients).

Before we turn to the proof of this theorem we add several remarks.

1. The proof of the theorem will show that if K ⊂ L then c_{1} in (1) can be replaced by c_{1}/2, and c_{3} in (3) by σ_{n}((3^{n−1} − 1)/2^{n−1})D^{n−2}.

2. Inequality (1) can be combined with (4) or (5), and (2) can be combined with (3) to yield inequalities relating the symmetric difference metric with the surface area deviation, namely

Δ_{v}(K, L) ≤ c_{1}c_{4}Δ_{s}(K, L)^{1/(n−1)} (n ≥ 3),
Δ_{v}(K, L) ≤ c_{1}c_{5}Δ_{s}(K, L)^{1/2} (n = 2),

and

Δ_{s}(K, L) ≤ c_{2}c_{3}Δ_{v}(K, L)^{1/n}.

Particularly if K ⊂ L these inequalities are of some interest and then the improvements of the coefficients mentioned in the previous remark are possible.

3. Inequalities (2), (4), and (5) can be viewed as quantitative versions of the fact that K ⊂ L implies v(K) ≤ v(L) and s(K) ≤ s(L). Indeed these inequalities show that if K ⊂ L and if K and L have in some direction support planes of distance at least ϵ, then v(K) ≤ v(L) − c_{2}^{−n}ϵ^{n}, s(K) ≤ s(L) − c_{4}^{1−n}ϵ^{n−1} if n ≥ 3, and s(K) ≤ s(L) − c_{5}^{−2}ϵ^{2} if n = 2.

4. If n = 2 and K ⊂ L, then (5) is essentially the same as a special case of an estimate of Vitale [6] for the L_{1}-metric.

Proof of the Theorem. In all parts of this proof the following conventions will be used. Hyperplanes will be referred to simply as ‘planes’. The unit ball in R^{n} (centered at o) will be denoted by B, and for any M ∈ K^{n} and u ⊂ S^{n−1} we let H_{M}(u) denote the support plane of M in the direction u. Furthermore, we frequently write only δ, Δ_{v}, and Δ_{s} instead of δ(K, L), Δ_{v}(K, L), and Δ_{s}(K, L), respectively.

The proof of (1) is a consequence of Steiner’s formula for the volume of a parallel body. If W_{i} denotes the i-th projection integral (Quermaßintegral) in R^{n} this formula states that for any λ ≥ 0

v(K + λB) = ∑_{i=0}^{n} \binom{n}{i}W_{i}(K)λ^{i}.

Letting λ = δ(K, L) and noting that W_{0}(K) = v(K) and

v(L) − v(K ∩ L) = v(K ∪ L) − v(K) ≤ v(K + δB) − v(K)  (6)

we obtain

v(L) − v(K ∩ L) ≤ ∑_{i=1}^{n} \binom{n}{i}W_{i}(K)δ^{i}.

Since, among all convex bodies of given diameter, W_{i} attains its maximum for balls (see Bonnesen-Fenchel [1, Sec. 54]) it follows that for all M ∈ K^{n}

W_{i}(M) ≤ 2^{i−n}κ_{n}(diam M)^{n−i}.  (7)

Hence, for any α > 0 we have

v(L) − v(K ∩ L) ≤ 2^{−n}κ_{n}D^{n−1}δ \frac{1}{α} ∑_{i=1}^{n} \binom{n}{i}(2α)^{i} (\frac{δ}{αD} )^{i−1} .

Letting α = (2^{1/n} − 1) /2 and assuming that δ/αD ≤ 1 we deduce that

v(L) − v(K ∩ L) ≤ κ_{n} \frac{(1 + 2α)^{n} − 1}{2α} (\frac{D}{2} )^{n−1} δ = \frac{κ_{n}}{2^{1/n} − 1} (\frac{D}{2} )^{n−1} δ.

But the same estimate holds if δ/αD > 1 since another application of (7) (with i = 0) shows that

v(L) − v(K ∩ L) ≤ 2^{−n}κ_{n}D^{n} ≤ 2^{−n}κ_{n}D^{n−1} \frac{δ}{α} = \frac{κ_{n}}{2^{1/n} − 1} (\frac{D}{2} )^{n−1} δ.

Combining this with the corresponding inequality for v(K) − v(K ∩ L) we obtain (1).

If K ⊂ L, then Δ_{v}(K, L) = v(L) − v(K ∩ L) and it is clear that c_{1} can be replaced by c_{1}/2 as stated in our first remark.

If λ ≥ 0 and K = B, L = (1+λ)B, then δ(K, L) = λ and Δ_{v}(K, L) = κ_{n}((1+λ)^{n}−1) ≥ nκ_{n}λ which shows that (3) cannot be improved in the sense stated in the theorem.

The analogue of (1) for the surface area, that is inequality (3), is more difficult to prove. The problem is that (6) rests on the fact that the inclusion K ∪L ⊂ K +δB implies v(K ∪ L) ≤ v(K + δB); but the corresponding inference for the surface area is not valid since, in general, K ∪ L is not convex. To surmount this difficulty we use the following concepts. If M ∈ K^{n}, o ∈ M, and u ⊂ S^{n−1} let ρ_{M}(u) denote the radial function of M, that is the length of the line segment M ∩ R(u), where R(u) denotes the ray {τu : τ ≥ 0}. Moreover, if o ∈ K ∩ L we define the radial distance between K and L by

δ_{ρ}(K, L) = sup{|ρ_{L}(u) − ρ_{K}(u)| : u ∈ S^{n−1}}.

For the proof of (3) let us now assume, as we may, that rB ⊂ K ∩ L. If u_{∗} ∈ S^{n−1} is such that δ is the distance between the respective support planes H_{K}(u_{∗}) and H_{L}(u_{∗}), then, considering the line segment from o to a point in ∂K ∩ H_{K}(u_{∗}) or ∂L ∩ H_{L}(u_{∗}) we see immediately that

δ_{ρ}(K, L) ≥ δ(K, L).  (8)

Next we show that

δ(K, L) ≥ \frac{r}{D} δ_{ρ}(K, L).  (9)

Interchanging, if necessary, the roles of K and L one can choose a u_{o} ∈ S^{n−1} such that

δ_{ρ}(K, L) = ρ_{L}(u_{o}) − ρ_{K}(u_{o}).

Let E_{K} denote the support plane of K at the point ∂K ∩ R(u_{o}) and let E_{L} be the plane parallel to E_{K} and containing ∂L ∩ R(u_{o}). Now, if h_{o} denotes the distance of o from E_{L}, and δ_{o} the distance between E_{K} and E_{L}, then elementary geometry shows that

δ_{ρ}(K, L) = \frac{ρ_{L}(u_{o})}{h_{o}}δ_{o} ≤ \frac{D}{r} δ_{o} ≤ \frac{D}{r} δ(K, L)

and this proves (9).

Using (8), (9), and the obvious fact that |ρ_{L}(u) − ρ_{K}(u)| ≥ |ρ_{L}(u) − ρ_{K∩L}(u)| (for all u ⊂ S^{n−1}) we deduce that

δ ≥ \frac{r}{D} δ_{ρ}(K, L) = \frac{r}{D} sup\{|ρ_{L}(u) − ρ_{K}(u)| : u ∈ S^{n−1}\}

≥ \frac{r}{D} sup\{|ρ_{L}(u) − ρ_{K∩L}(u)| : u ∈ S^{n−1}\} = \frac{r}{D} δ_{ρ}(L, K ∩ L)

≥ \frac{r}{D} δ(L, K ∩ L).

Thus, δ ≥ (r/D)δ(L, K ∩ L) and similarly one finds δ ≥ (r/D)δ(K, K ∩ L). It follows that K ⊂ (K ∩ L) + (D/r)δB and L ⊂ (K ∩ L) + (D/r)δB, and this implies

Δ_{s} ≤ 2 (s ((K ∩ L) + \frac{D}{r} δB) − s(K ∩ L)) .  (10)

We now use Steiner’s formula for the surface area which states that for any M ∈ K^{n} and ϵ ≥ 0

s(M + ϵB) = n ∑_{i=0}^{n−1} \binom{n − 1}{i}W_{i+1}(M)ϵ^{i}  (11)

(see Hadwiger [4, p. 214]). Letting ϵ = (D/r)δ, M = K ∩ L and using (10) together with the relation nW_{1}(M) = s(M) we find that

Δ_{s} ≤ 2n ∑_{i=1}^{n−1} \binom{n − 1}{i}W_{i+1}(K ∩ L) (\frac{D}{r} δ)^{i} .

This, combined with (7) and the obvious estimate δ/D ≤ 1, yields

Δ_{s} ≤ σ_{n}2^{2−n}D^{n−1} ∑_{i=1}^{n−1} \binom{n − 1}{i} (\frac{2D}{r} )^{i} (\frac{δ}{D} )^{i} ≤ σ_{n}2^{2−n}D^{n−2}δ ((\frac{2D}{r} + 1)^{n−1} − 1) .

Observing also that 1 ≤ D/2r, we obtain (3).

If K ⊂ L, then

Δ_{s} = s(L) − s(K) ≤ s(K + δB) − s(K).

Using again (7) and (11) (with M = K and ϵ = δ), one finds

Δ_{s} ≤ σ_{n}2^{1−n}D^{n−1} ∑_{i=1}^{n−1} \binom{n − 1}{i}2^{i} (\frac{δ}{D} )^{i} ≤ σ_{n} \frac{3^{n−1} − 1}{2^{n−1}}D^{n−2}δ,

which justifies the corresponding statement in our first remark.

The same example as that used in connection with inequality (1) shows that no essential improvement of (3) is possible.

We now prove (2). Without any loss in generality it can be assumed that rB ⊂ K ∩L. There exists a direction u_{o} such that, with proper designation of K and L,

δ = h_{L}(u_{o}) − h_{K}(u_{o}).

Let p ∈ L ∩ H_{L}(u_{o}) and let C be the smallest cone that contains rB, has apex p and whose base is in H_{(rB)}(−u_{o}). If J denotes the slab bounded by H_{K}(u_{o}) and H_{L}(u_{o}) then the cone C̃ = C ∩ J is similar to C and it is obvious that Δ_{v} ≥ v(C̃). Let Q denote the largest ball in C with center in H_{K}(u_{o}), and let ρ denote the radius of Q. Then we have ρ/r = δ/h_{L}(u_{o}) and therefore ρ ≥ (r/D)δ. Also, since the base of C̃ contains the (n − 1)-dimensional ball H_{K}(u_{o}) ∩ Q, the ((n − 1)-dimensional) volume of the base of C̃ is at least κ_{n−1}ρ^{n−1}. Hence,

Δ_{v} ≥ v(C̃) ≥ \frac{κ_{n−1}}{n} ρ^{n−1}δ ≥ \frac{κ_{n−1}}{n} (\frac{r}{D} )^{n−1} δ^{n},

and this proves (2).

That the exponent of Δ_{v}(K, L) in (2) cannot be improved is seen by letting K be a right cone with spherical base, and L the truncated cone obtained by cutting off from K (with a plane parallel to its base) the cone similar to K of height δ.

For the proof of (4) and (5) we first consider two convex bodies M and N in R^{n} such that rB ⊂ M ⊂ N and derive a lower bound for Δ_{s}(M, N) in terms of δ̂ = δ(M, N), r, and D̂ = max {diam M, diam N}. Clearly, there is a u_{o} ∈ S^{n−1} such that

δ(M, N) = h_{N}(u_{o}) − h_{M}(u_{o}).

Let H_{M}^{+}(u_{o}) be the closed half-space bounded by H_{M}(u_{o}) and containing M, and let M′ = N ∩ H_{M}^{+}(u_{o}). Obviously,

δ(M, N) = δ(M′, N).  (12)

Also, since Δ_{s}(M′, N) ≤ Δ_{s}(M, N) and Δ_{s}(M′, N) = s_{o} − s(N ∩ H_{M}(u_{o})), where s_{o} denotes the surface area of the part of ∂N not lying in ∂M′, we have

Δ_{s}(M, N) ≥ s_{o} − s(N ∩ H_{M}(u_{o})).  (13)

Let now ℓ be a line orthogonal to h_{M}(u_{o}), and let us perform a spherical symmetrization (Schwarzsche Abrundung, see Bonnesen-Fenchel [1, Sec. 41]) of M′ and N with ℓ as axis. It transforms these bodies into rotationally symmetric bodies, say M̄′ and N̄. Moreover, N ∩ H_{M}(u_{o}) is transformed into an (n − 1)-dimensional ball, say G, that lies in the plane H_{M}(u_{o}) and has its center in ℓ. Since spherical symmetrization preserves volume and does not increase surface area it follows from (13) that

Δ_{s}(M, N) ≥ s̄_{o} − s(N̄ ∩ H_{M}(u_{o})),  (14)

where s̄_{o} is defined as s_{o} but with respect to N̄ and M̄′ rather than N and M′. Let now C denote the cone with apex q = H_{N}(u_{o}) ∩ ℓ and base G, and let s̃ denote the lateral surface area of C. Then, s̃ ≤ s̄_{o}, and it follows from (14) that

Δ_{s}(M, N) ≥ s̃ − s(N̄ ∩ H_{M}(u_{o})).  (15)

Furthermore, if G has radius ρ, then

s̃ = κ_{n−1}ρ^{n−2}\sqrt{δ̂^{2} + ρ^{2}},

and (15) implies therefore

Δ_{s}(M, N) ≥ κ_{n−1}ρ^{n−2}(\sqrt{ρ^{2} + δ̂^{2}} − ρ) = κ_{n−1} \frac{ρ^{n−2}δ̂^{2}}{(δ̂^{2} + ρ^{2})^{1/2} + ρ}.  (16)

Since rB ⊂ N the body N̄ contains a ball, say O, of radius r with center on ℓ. Consider a line T that contains q and is tangent to O. Let η denote the distance between the center of G and T ∩ G, and t the distance between q and the point T ∩ O. Then we deduce, observing also (12), that t/r = δ̂/η and consequently

ρ ≥ η = \frac{r}{t} δ̂ ≥ \frac{r}{D̂} δ̂.

Combining this with (16) we infer that

Δ_{s}(M, N) ≥ κ_{n−1} \frac{ρ^{n−3}δ̂^{2}}{((D̂/r)^{2} + 1)^{1/2} + 1}.

If n ≥ 3 then ρ^{n−3} is increasing or constant and therefore

Δ_{s}(M, N) ≥ κ_{n−1} \frac{(r/D̂)^{n−3}}{((D̂/r)^{2} + 1)^{1/2} + 1}δ̂^{n−1}.

Since 1 ≤ D̂/2r this yields

Δ_{s}(M, N) ≥ κ_{n−1} (\frac{r}{D̂} )^{n−2} \frac{2}{\sqrt{5} + 1}δ̂^{n−1}.  (17)

The desired inequality (4) is now obtained by adding the two inequalities that result by substituting into (17) M = K ∩ L and N = K or N = L, and noting that D̂ ≤ D, δ(K, K ∩ L)^{n−1} + δ(L, K ∩ L)^{n−1} ≥ (max {δ(K, K ∩ L) , δ(L, K ∩ L)})^{n−1} ≥ δ(K, L)^{n−1}, and Δ_{s}(K, L) = Δ_{s}(K, K ∩ L) + Δ_{s}(L, K ∩ L).

That the exponent of Δ_{s}(K, L) cannot be improved is seen by the same example as that described in connection with (2).

All conclusions of this proof up to and including inequality (16) remain valid if n = 2. Thus, in this case we have

Δ_{s}(M, N) ≥ 2\frac{δ̂^{2}}{(δ̂^{2} + ρ^{2})^{1/2} + ρ},

and since δ̂ ≤ D̂, ρ ≤ D̂ it follows that

Δ_{s}(M, N) ≥ \frac{2}{(\sqrt{2} + 1)D̂} δ̂^{2}.

Letting again M = K ∩ L and N = K or N = L and proceeding as before we obtain (5). Note that (5) is trivially satisfied if int (M ∩ N) = ∅ and int (M ∩ N) ≠ ∅.

It is remarkable that the case n = 2 is really exceptional. To show that in (5) the exponent 1/2 cannot be replaced by a larger number consider the following example. In the usual (x, y)-coordinate system let K be the convex domain bounded by y = 0 (−1 ≤ x ≤ 1) and the curve y = 1 − x^{m} (−1 ≤ x ≤ 1), where m is a positive even integer. Furthermore, assuming that an ϵ ∈ [0, 1] is given, let L be defined as the part of K where y ≤ 1−ϵ. Clearly, δ(K, L) = ϵ and Δ_{s}(K, L) ≥ 2(\sqrt{ϵ^{2} + ϵ^{2/m}} −ϵ^{1/m}) = 2ϵ^{2}/(\sqrt{ϵ^{2} + ϵ^{1/m}} + ϵ^{1/m}) ≥ (2/(\sqrt{2} + 1))ϵ^{2−1/m}. Since m can be arbitrarily large this justifies our assertion.

References

[1] Bonnesen, T.; Fenchel, W.: Theorie der konvexen Körper. Ergebn. d. Math., Bd. 3, Springer Verlag, Berlin 1934. (Engl. transl.: Theory of Convex Bodies BCS Assoc. Moscow, Idaho 1987.)

[2] Florian, A.: On a metric for the class of compact convex sets. Geom. Dedicata 30 (1989), 69–80.

[3] Gruber, P. M.: Approximation of convex bodies. Handbook of Convex Geometry, vol. A. North-Holland, Amsterdam - London - New York - Tokyo 1993.

[4] Hadwiger, H.: Vorlesungen über Inhalt, Oberfläche und Isoperimetrie. Grundlehren der Math. Wiss. Bd. 93. Springer-Verlag, Berlin - Göttingen - Heidelberg 1957.

[5] Shephard, G. C.; Webster, R. J.: Metrics for sets of convex bodies. Mathematika 12 (1965), 73–88.

[6] Vitale, R.: L_{p} metrics for compact convex sets. J. Approx. Theory 45 (1985), 280–287.

Received November 18, 1998