The technique of M-regions and cap coverings: a survey

Imre Bárány ^{∗} Mathematical Institute of the Hungarian Academy of Sciences H-1364 Budapest Pf. 127 Hungary

                barany@math-inst.hu

and Department of Mathematics University College London Gower Street, London, WC1E 6BT, UK

June 28, 2001

Abstract. Everything interesting that can happen to a convex body happens near its boundary. The technique in the title is a method to deal with the boundary structure of convex bodies. Its power will be illustrated on several examples: random polytopes, floating bodies, lattice polytopes, approximation problems, and on a problem from computational geometry.

∗Partially supported by Hungarian National Science Foundation Grant T 016391

1 Introduction

Macbeath-regions, or M-regions, for short, were introduced in 1952 by A. M. Macbeath [Ma52]: given a convex body (i.e., a compact, convex set with nonempty interior) K ⊂ R^{d}, and a point x ∈ K, the corresponding M-region is, by definition,

M_{K}(x) = M(x) = K ∩ (2x − K).

So M(x) is, again, a convex set. It is centrally symmetric with centre x. Define the function u : K → R by

u(x) = vol M(x).

Macbeath [Ma52] made two important observations :

• If x is a vertex of conv(K ∩ ℤ^{d}), the integer convex hull of K, then u(x) ≤ 2^{d}.

• The function u^{1/d} is concave. Thus its level sets

K(u ≥ t) = {x ∈ K : u(x) ≥ t}

are convex for every t ≥ 0.

The first observation follows from Minkowski’s classical theorem, and the second is implied by the Brunn-Minkowski inequality upon noticing that M(\frac{1}{2}(x + y)) ⊂ \frac{1}{2}(M(x) + M(y)).

How many vertices does the integer convex hull have? This is a natural question in integer programming, especially when K is a convex (rational) polytope, since then the vertices of the integer hull constitute the set of solutions to the integer programming problems (as c varies): maximize cx subject to the conditions x ∈ K and x ∈ ℤ^{d}.

The first observation shows that the set of vertices of the integer convex hull are contained in K(u ≤ 2^{d}). What one would be tempted to think (at least when K is in “generic” position with respect to ℤ^{d} and has large volume) is that the number of vertices of conv(K ∩ ℤ^{d}) is essentially equal to vol K(u ≤ 2^{d}).

Is this indeed true? And if so, how to determine vol K(u ≤ 2^{d}), or more generally, vol K(u ≤ t)? We will return to these questions later. But what is probably more important is that the introduction of M-regions and the function u leads to immediate insight, questions, and conjectures.

This survey explains how M-regions and cap coverings can be used in a wide variety of problems. Emphasis is on the method and its applications, and not on actual proofs. Most of the material comes from published papers where the details can be found. The proof of Theorems 11, 12, and 13 are new and are here to further illustrate how the method works.

2 Notation

In this chapter we collect the necessary notation. This is not so much for the readers to memorize, but for their convenience should they wish to refer back to a definition.

K^{d} or just K is the set of all convex bodies in R^{d} and K_{1} stands for those K ∈ K that have unit volume: vol K = 1. The boundary of K is denoted by bd K. We write aff S and conv S for the affine and convex hull of S.

The M-region of K ∈ K with center x is denoted by M(x), and its λhomothetic copy by (see section 3)

M(x, λ) = M_{K}(x, λ) = x + λ [(K − x) ∩ (x − K)] .

A cap C of K ∈ K is the intersection of K with a closed halfspace H, its width is the usual width in the normal direction of H. Given λ ≥ 1 and a cap C = K ∩ H define C^{λ} as the cap containing C, and having bounding hyperplane parallel to that of H but with width λ times as large as the width of C (section 4).

The function v : K → R (defined in section 4) is

v(x) = min{vol(K ∩ H) : x ∈ H, and H is a halfspace}.

A minimal cap belonging to x is a cap C(x) with x ∈ C(x) and vol C(x) = v(x).

The level sets of v are K(v ≤ t), K(v ≥ t) (section 4). We call K(v ≥ t) the floating body of K with parameter t > 0, and the wet part is

K(t) = K(v ≤ t) = {x ∈ K : v(x) ≤ t}.

K_{n} = conv{x_{1}, …, x_{n}} is the random polytope inscribed in K, (see section 4). The expectation of vol K − vol K_{n} is denoted by E(K, n). The number of k-dimensional faces of the polytope P is f_{k}(P). T (P) stands for the number of towers (or flags) of P (see section 4)

It will be convenient to use the ≪, ≫ and ≈ notation. For instance, f(n) ≪ g(n) means that there is a constant b such that f(n) ≤ bg(n) for all values of n. This notation always hides a constant which, as a rule, will depend on dimension only.

3 Segments on the surface of K

The technique of M-regions and cap coverings was invented by Ewald, Larman, and Rogers in their seminal paper [ELR70]. Their aim was to answer a beautiful and inspiring question of Vic Klee [Kl57], [Kl69]: “Can the boundary of a convex body contain segments in all directions?” (this is the title of [Kl69].) After partial results by McMinn, Besicovitch, Pepe, and Grünbaum and Klee the following basic result was proved in [ELR70].

THEOREM 1 Let S(K) denote the set of unit vectors v ∈ R^{d} such that the boundary of the convex body K ⊂ R^{d} contains a segment parallel with v. Then S(K) has σ-finite (d − 2)-dimensional Hausdorff measure.

The proof is based on a sequence of lemmas that lie at the core of the method this paper is about. First we define the blown-up version of the M-region:

M(x, λ) = M_{K}(x, λ) = x + λ [(K − x) ∩ (x − K)] .

This is just a blown-up copy of M(x) from its center x with scalar λ > 0.

LEMMA 1 If x, y ∈ K and M(x, 1/2) ∩ M(y, 1/2) ≠ ∅, then M(y, 1) ⊂ M(x, 5).

For a closed halfspace H the set K ∩ H is called a cap of K if it is nonempty. Its width is the usual width in the normal direction of H.

LEMMA 2 Assume K ∈ K contains a ball of radius r and the halfspace H is disjoint from the ball. If the width of the cap K ∩ H is at most r/2, then

K ∩ H ⊂ M(x, 3d)

where x is the center of gravity of the part of K lying in the bounding hyperplane of H.

LEMMA 3 Assume K ∈ K contains a ball of radius r and is contained in a ball of radius R. Given a positive ε ≤ ε_{0}, there are caps C_{1}, …, C_{m} with

(i) bd B ⊂ ∪_{1}^{m}C_{i},

(ii) the minimal width of C_{i} is between 2ε and 36dε,

(iii) ∑_{1}^{m} vol C_{i} ≪ ε vol K

Here ε_{0} and the constant in ≪ depends on d, r, R only.

Thus the caps C_{i} constitute an “economic cap covering” of bd K in the sense that each C_{i} has minimal width ≈ ε and their total volume is ≪ ε vol K. We will see later several versions and strengthenings of this result. It is worth mentioning that the economic cap covering lemma is a relative the Besicovitch covering theorem.

Theorem 1 says that, for every convex body, the set of exceptional directions is small. Precisely, it has σ-finite 1-codimensional Hausdorff measure. (Exceptional direction means here a direction contained in bd K.) That the exceptional set is small is important and useful in other cases as well, for instance, in integral geometry. It is shown in [ELR70] that the set of exceptional r-flats has σ-finite 1-codimensional Hausdorff measure in the space of all r-flats. (Here K ∈ K, of course, and an r-flat is exceptional if it intersects bd K in a set of dimension r.)

The method of [ELR70] was simplified a little by Zalgaller [Za72], and developed further by Ivanov [Iv76], and Schneider [Schn78], [Schn99]. Ivanov shows that the union of all lines in R^{d} that meet bd K in a segment has σ-finite (d − 1)-dimensional Hausdorff measure. A consequence is that for almost all points x ∉ K the shadow boundary of K under central projection from x is sharp. (The reader will have no difficulty stating the analogous consequence of Theorem 1.) The following results of Schneider [Schn78] and [Schn99] have applications in integral geometry. The proof method is based on that of [ELR70] but is much more involved.

THEOREM 2 Let K, K′ ∈ K. The set of all rotations ρ ∈ SO(d) for which K and ρK′ contain parallel segments lying in parallel supporting hyperplanes has σ-finite 1-codimensional Hausdorff measure.

THEOREM 3 Let K, K′ ∈ K. The set of all rigid motions ρ for which K and ρK′ have an exceptional common boundary point is of Haar measure zero.

Here a point x, common to bd K and bd K′, is exceptional if the normal cones to K at x and to K′ at x contain a common halfline.

Schneider gives a sketch of the proof of Theorem 1 in [Schn98], and a full proof, containing Zalgaller’s simplification, in his excellent book [Schn93]. The interested reader is advised to consult these references.

4 Random polytopes

Assume K ∈ K_{1} and choose points x_{1}, …, x_{n} randomly, independently, and according to the uniform distribution from K. Then K_{n} = conv{x_{1}, …, x_{n}} is a random polytope. It is intuitively clear that, with high probablilty, K_{n} gets nearer and nearer to K as n goes to infinity. There has been a lot of research to determine how well K_{n} approximates K in various measures of approximation, a good source of information is the survey [WW93]. These measures are typically the expectation of ϕ(K) − ϕ(K_{n}) where ϕ is a functional defined on K, like volume, surface area, mean width, etc. We will mainly consider the volume and set

E(K, n) = E(vol K − vol K_{n}).

E(K, n) was first investigated by Rényi and Sulanke in [RS63], d = 2 polygons and smooth convex sets, and then by Wieacker [Wi78], d = 3 smooth bodies, and d ≥ 2 and K the unit ball. Groemer [Gro74] showed that among all convex bodies of unit volume E(K, n) is maximal for the ellipsoids (and only for them). The general behaviour of E(K, n) was understood in [BL88]. To explain their results define the function v : K → R by

v(x) = min{vol(K ∩ H) : x ∈ H, and H is a halfspace},

and for t > 0 set

K(v ≤ t) = {x ∈ K : v(x) ≤ t}.

Note that K(v ≥ t) is the floating body of K corresponding to t (cf [Bl23] and [Le98]. The floating body is the intersection of halfspaces so it is convex. With this terminology K(v ≤ t) is the “wet part” of K (cf. [Bl23]) for which it will be convenient to introduce the notation

K(t) = K(v ≤ t).

The general principle governing E(K, n) is that it is of the same order of magnitude as the volume of the wet part with t = 1/n. Precisely, we have

THEOREM 4 For K ∈ K_{1} and n ≥ d + 1

vol K(1/n) ≪ E(K, n) ≪ vol K(1/n).

The proof of this theorem is based, to a great extent, on the technique of M-regions and cap coverings. We need some more definitions: Given x ∈ K, a cap C(x) containing x and satisfying vol C(x) = v(x) is called a minimal cap. Note that the minimal cap is not unique. Given λ ≥ 1 and a cap C = K ∩ H with H the halfspace, define C^{λ} as the cap containing C, and having bounding hyperplane parallel with that of H but with width λ times as large as the width of C.

The economic cap covering result for the inner parallel body, Lemma 3, can be extended for the wet part K(ε) as follows.

LEMMA 4 Let ε_{0}(d) = (2d)^{−2d}. Given K ∈ K_{1} and a positive ε < ε_{0}, there exist caps C_{1}, …, C_{m} and pairwise disjoint convex sets C′_{1}, …, C′_{m} with C′_{i} ⊂ C_{i} such that

(i) ∪_{1}^{m}C′_{i} ⊂ K(ε) ⊂ ∪_{1}^{m}C_{i}

(ii) vol C_{i} ≪ ε, (i = 1, …, m), and vol C′_{i} ≫ ε, (i = 1, …, m).

Thus K(ε) is covered by caps of volume ≈ ε without much overcovering. It is also clear that m ≈ vol K(ε)/ε. We will sketch the proof of this basic result soon. It is based on Lemma 1 and the following extension of Lemma 2

LEMMA 5 If x ∈ K and v(x) < ε_{0}, then

C(x) ⊂ M(x, 3d)

for every minimal cap C(x).

Since trivially M(x) ⊂ C^{2}(x), Lemma 5 establishes the “equivalence” of the M-region M(x) and a minimal cap C(x): a blown up copy of M(x) contains C(x) and a blown up copy of C(x) contains M(x). Here the blow-up factors depend on dimension only. Thus M-regions and minimal caps can be interchanged freely, without loosing more than a constant factor in estimates. As a consequence, for instance, we have that u(x) ≈ v(x) as long as they are small enough:

LEMMA 6 Given K ∈ K_{1} we have

• u(x) ≤ 2v(x) for all x ∈ K,

• v(x) ≤ (3d)^{d}u(x) if either v(x) ≤ ε_{0} or if u(x) ≤ (3d)^{−3d}.

Here is the sketch of proof of Lemma 4 which is similar to that of Lemma 3 and which serves as a model proof for other applications as well. Let x_{1}, …, x_{m} be a maximal collection of points from the boundary of the floating body K(v ≥ ε), maximal with respect to the property that M(x_{i}, 1/2) ∩ M(x_{j}, 1/2) = ∅ for all pairs 1 ≤ i < j ≤ m. Using the maximality of the system, Lemma 1, and some simple volume estimations it is not difficult to see that the M-regions M(x_{i}, 5) constitute a covering of the wet part K(ε). On the other hand, take any halfspace H_{i} with x_{i} ∈ H_{i} which is disjoint from the interior of K(v ≥ ε). Then C′_{i} = M(x_{i}, 1/2) ∩ H_{i} lies completely in the wet part K(ε) and also in M(x_{i}, 5), and they are pairwise disjoint. Also, vol M(x_{i}, 5) ≪ ε and vol C′_{i} ≫ ε. Thus, the M-regions M(x_{i}, 5), together with C′_{i} form an economic covering of the wet part. To turn it into an economic cap covering one has to replace the M(x_{i}, 5) by caps C_{i} that are obtained from minimal caps C(x_{i}) via C_{i} = C(x_{i})^{λ}. Here λ can be taken to be 6. This can be seen from the equivalence of M(x) and C(x) and the fact that M(x, 5) ⊂ C^{6}(x). Details are in [BL88].

Before we proceed we state two lemmas from [Bá89] that will be needed later. The first is rather simple, and the second is a stronger version of Lemma 5.

LEMMA 7 Assume K ∈ K, t > 0. Then K(v ≥ t) contains no segment in its boundary.

LEMMA 8 Suppose K ∈ K_{1}, 0 < ε < ε_{0}, and let C be a cap of K such that C ∩ K(v ≥ ε) is a single point x. Then

C ⊂ M(x, 3d) and ε ≤ vol C ≤ dε.

These two lemmas say that, for small enough ε, any tangent hyperplane to K(ε) has a single common point with K(v ≥ ε), and that this tangent hyperplane cuts off a cap C from K with ε ≤ vol C ≤ dε. Moreover, C ⊂ M(x, 3d) where x denotes the common point of the hyperplane and K(v ≥ ε).

We mention further that the equivalence of M(x) and C(x) can be used to obtain a good lower bound for the volume of the wet part (Theorem 2 of [BL88]).

THEOREM 5 For every K ∈ K_{1} and every t ∈ [0, 1/2],

t log^{d−1} \frac{1}{t} ≪ vol K(t).

This is the counterpart of the affine isoperimetric inequality (cf [Bl23],

[Le98] ):

THEOREM 6 For every K ∈ K_{1} and every t ∈ [0, 1/2],

vol K(t) ≪ t^{\frac{2}{d+1}} .

These theorems show that for K ∈ K_{1},

t log^{d−1} \frac{1}{t} ≪ vol K(t) ≪ t^{\frac{2}{d+1}} .

The best constant in Theorem 5 is probably the one for the simplex, but this is a difficult open question. The order of magnitude of the lower bound is, however, best possible, as shown by polytopes see [BL88]. The best constant in Theorem 6 is for the ball (or ellipsoid), and the order of magnitude is t^{2/d+1}, as t → 0, for all convex bodies that have a smooth piece on their boundary (see [BL88] for the precise statement) . Using these facts, a general result of Gruber [Gru83] says that for a generic (in Baire category sense) convex body K ∈ K_{1} the volume of the wet part wildly fluctuates between these two bounds, as t goes to zero, (see [Gru83] or [BL88] for a precise statement). This implies that there is no hope to determine vol K(t) for a generic convex body.

However, more can be said about E(K, n) and vol K(t) (as t → 0) in the case of smooth convex bodies and polytopes.

For instance, for polytopes, using cap coverings and further properties of M-regions the following result was proved by Bárány and Buchta [BB93]. Let T (P) denote the number of towers of the polytope P, i.e., T (P) is the number of chains F_{0} ⊂ F_{1} ⊂ … ⊂ F_{d−1}, where F_{i} is an i-dimensional face of P.

THEOREM 7 For a polytope P ∈ K_{1} as n goes to infinity,

E(P, n) = \frac{T (P)}{(d + 1)^{d−1}(d − 1)!} \frac{log^{d−1} n}{n} (1 + o(1)) .

The proof in [BB93] shows also that most of the volume missed by P_{n} is concentrated in small simplices associated with the towers of P. The same asymptotic was proved for simple polytopes by Affentranger and Wieacker [AW91] using integral geometric tools. Their result is used in [BB93] to determine the missed volume in the associated small simplices. Another feature of the proof is “independence of shape”: the missed volume near a fixed point of the boundary is almost independent of other parts of the boundary.

The result in [BB93] extends to vol P (t) as well:

vol P (t) = \frac{T (P)}{2^{d}d!(d − 1)!}t (log \frac{1}{t})^{d−1} (1 + o(1)) .

In the case of smooth convex bodies it has been known (cf. [Bl23], [Le98]) that

vol K(t) = const ∫_{bd K} κ^{1/d+1}dSt^{2/d+1} (1 + o(1)) ,

where κ is the (product) curvature and the constant depends only on d. Whether a similar asymptotic formula holds for E(K, n), a question of Schneider, was answered in [Bá92] in the affirmative when K is C^{3} with nonvanishing curvature. The proof uses the cap covering technique and independence of shape. Later Schütt [Schü94] extended this result for all convex bodies.

At this point we can answer one of the questions from the introduction, namely, the one about the volume of K(u ≤ 2^{d}) (assuming vol K is large). Note first that for K ∈ K, not necessarily of unit volume, the quantity

\frac{vol K(v ≤ ε vol K)}{vol K}

is invariant under nonsingular affine transformations. Then, with ε = 2^{d}/ vol K and assuming vol K is so large that ε < ε_{0}

vol K(u ≤ 2^{d}) ≈ vol K(v ≤ 2^{d}) = K(v ≤ ε vol K).

As we just saw, there is no hope to determine this for a generic convex body. But for polytopes, this is approximately equal to (log vol K)^{d−1}, and for smooth convex bodies it is to (vol K)^{\frac{d−1}{d+1}} .

An application of the cap covering Theorem (Lemma 4), and an important step in the proof of Theorem 4, is the following

THEOREM 8 If K ∈ K_{1} and ε ≤ ε_{0} and λ > 1, then

vol K(ε) ≪ λ^{−d} vol K(λε).

This expresses a concavity type property, at t = 0, of the function t ↦ vol K(t). It is an interesting open question whether some natural function of vol K(t), for instance its dth root, is concave at t = 0.

Let’s now return to random polytopes and denote, as usual, by f_{k}(P) the number of k-dimensional faces of the polytope P. It is very simple to see that the expected number, E(f_{0}(K_{n})), of vertices of the random polytope K_{n} is equal to nE(K, n − 1). Although such precision is out of reach for Ef_{k}(K_{n}), the expected number of k-dimensional faces of K_{n}, the asymptotic behaviour was determined in [Bá89].

THEOREM 9 If K ∈ K_{1} and k ∈ {0, 1, …, d − 1}, then

n vol K(1/n) ≪ Ef_{k}(K_{n}) ≪ n vol K(1/n).

It is perhaps instructive to explain here how a strengthened version of the economic cap covering Lemma 4 is used in the proof of Theorem 9. We will work in the case k = d−1. First, the strengthened version is the same (apart from the constants in ≪ and ≫) as Lemma 4 with the extra condition:

(iii) For every cap C of K with vol C ≤ ε there is a i ∈ {1, …, m} such that C ⊂ C_{i}.

Next one needs a good estimate for the measure of the set S(ε) of those d-tuples (x_{1}, …, x_{d}) ∈ K × … × K whose affine hull A = aff{x_{1}, …, x_{d}} avoids K(ε). Actually, what is needed is

meas S(v ≥ ε) ≪ ε^{d−1} vol K(ε).

This is what we will show here, for the rest of the proof we refer the reader to [Bá89].

It is not hard to see that if A ∩ K(v ≥ ε) = ∅, then A ∩ K is contained in a cap C of volume at most ε. Thus

S(ε) ⊂ ∪ {(C, …, C) : C is a cap with vol C ≤ ε} ⊂ ∪_{1}^{m}(C_{i}, …, C_{i}).

Consequently,

meas S(ε) ≤ meas (∪_{1}^{m}(C_{i}, …, C_{i})) ≤ ∑_{1}^{m}(vol C_{i})^{d}
≪ ∑_{1}^{m} ε^{d−1} vol C_{i} ≪ ∑_{1}^{m} ε^{d−1} vol C′_{i} ≪ ε^{d−1} vol K(ε).

We mention finally that the equivalence of K \ K_{n} and the wet part K(1/n), expressed in Theorem 4 extends to further measures of approximation, see [WW93] or [Bá89].

5 Halfspace range searching

Assume you are given a set S of n points in d space, with their coordinates, say, and you have to answer questions, actually lots of questions of the form “How many points of S lye in the halfspace H = H(a, t) given by the inequality ax ≤ t?” It is easy to answer in n steps: you just count how many of the points of S satisfy this inequality. In this case the answer takes n units of time (one unit for each s ∈ S to decide whether as ≤ t or not), and it takes very little memory space: you only have to keep one memory cell to count how many points of S are in H.

But you want to answer these questions faster. You may take some preparations (called preprocessing): once there are going to be many questions to be answered this will pay off. One method is based on noticing that there are only finitely many ways to cut S by halfspaces. So call halfspaces H_{1} and H_{2} equivalent if S ∩ H_{1} = S ∩ H_{2}, and record, in a catalogue, the number of elements in S ∩ H for one halfspace from each equivalence class. Then to answer the question H you only have to find the hafspace in the catalogue equivalent to H. Assuming that this takes little time, the answers come very fast, but the number of memory cells is as large as the size of the catalogue, essentially \binom{n}{d−1}.

Even these two simple examples suggest that there is a trade-off between memory and time. The best known algorithm, due to J. Matoušek [Mat93], shows that with memory size m, and after preprocessing, the answers to this so-called halfspace range searching take at most

const\frac{n}{m^{1/d}}

time. This is conjectured to be optimal. (Partial confirmation comes from a result of Chazelle that establishes an almost matching lower bound for range searching for slabs instead of halfspaces, cf [Ch89].)

A lower bound, which is not very far from this upper bound was proved by Brönniman, Chazelle, and Pach in [BCP93]. Even stating their result precisely would go beyond the limits of this survey. It says, roughly, that in a certain model of computation, it is impossible to answer halfspace range searching questions faster than

const\frac{n}{m^{1/d}} (\frac{log n}{n})^{\frac{d−1}{d(d+1)}} ,

which is fairly close to the above upper bound. Here n is the number of points in d-space, and the memory size is m. The proof of this result uses, among other tools, combinatorics, integral geometry, an isoperimetric inequality, and, most important from our point of view, M-regions and cap coverings. This is the so called slicing lemma (Lemma 2.4 in [BCP93]) and this is what we are going to explain in more detail.

LEMMA 9 Given K ∈ K_{1} and ε ∈ (0, ε_{0}), there exist convex sets K_{1}, …, K_{m} such that

• m ≪ vol K(ε)/ε,

• vol K_{i} ≫ ε,

• every cap C of K, of volume ε contains one of the K_{i}.

This follows from an extension of the economic cap covering Lemma 4 with the extra condition

(iv) for every cap C of K with vol C ≥ ε there is a i ∈ {1, …, m} such that C′_{i} ⊂ C.

This is a neat counterpart of the extension (iii) of Lemma 4 (after Theorem 9). Actually Lemma 4 holds with both extension (iii) and (iv) simultaneously. For the proof of the slicing lemma, one should take K_{i} = C′_{i}. The proof in [BCP93] is different and uses an interesting variant of Lemma 1:

LEMMA 10 If x, y ∈ K and M(x, 1/5) ∩ M(y, 1/5) ≠ ∅, then M(y, 1/5) ⊂ M(x, 1).

6 Lattice polytopes

In 1963 G. E. Andrews [An63] proved a remarkable theorem saying that a lattice polytope P ⊂ R^{d} of volume V > 0 cannot have more than

const V ^{\frac{d−1}{d+1}}

vertices or facets. Alternative proofs were later found by Arnol’d [Ar80], Konyagin and Sevastyanov [KS84], Schmidt [Schm85], Bárány and Vershik [BV92]. Here is yet another proof, from [BL98], based on the technique of M-regions. What we will present here is a sketch of the proof of

f_{d−1}(P) ≪ V ^{\frac{d−1}{d+1}}

since this is a novel application of the technique of M-regions and capcoverings.

We start the proof by fixing ε = (2d(15d)^{d}(d + 1)!V)^{−1}. Note that in this way εV < ε_{0}. Let F be a facet of P and let x_{F} be the point on bd P (v ≥ εV) where the tangent hyperplane to P (v ≥ εV) is parallel with F. According to Lemma 7, x_{F} is unique. Let C_{F} stand for the cap cut off from K by the hyperplane parallel with F and passing through x_{F}.

LEMMA 11 For distinct facets F and G of P

M(x_{F} , 1/2) ∩ M(x_{G}, 1/2) = ∅.

To see this assume this intersection is nonempty. Then by Lemma 1 M(x_{G}, 1) ⊂ M(x_{F} , 5). Further, Lemma 8 shows that

G ⊂ C_{G} ⊂ M(x_{G}, 3d) ⊂ M(x_{F} , 15d),

where the last containment is a simple consequence of M(x_{G}, 1) ⊂ M(x_{F} , 5). Even simpler is

F ⊂ C_{F} ⊂ M(x_{F} , 3d) ⊂ M(x_{F} , 15d).

Now M(x_{F} , 15d) contains both facets F and G so it contains d + 1 affinely independent lattice points. Thus its volume is at least 1/d!. Then, using again Lemma 8,

\begin{aligned}\frac{1}{d!} & ≤ vol M(x_{F} , 15d) = (15d)^{d}u(x_{F}) ≤ (15d)^{d}2v(x_{F}) \\ & ≤ 2(15d)^{d}dεV = \frac{1}{(d+1)!}. \end{aligned}

A contradiction (due to the choice of ε), finishing the proof.

So the half M-regions M(x_{F} , 1/2), for all facets F are pairwise disjoint. Their “half” M(x_{F} , 1/2)∩C(F) lies completely in P (ε). Then, by the general version Theorem 6

∑ \frac{1}{2} vol M(x_{F} , 1/2) ≤ vol P (v ≤ εV) ≪ ε^{\frac{2}{d+1}} V ≪ V ^{\frac{d−1}{d+1}} .

Now, again by Lemma 8 Lemma 6,

vol M(x_{F} , 1/2) = 2^{−d}u(x_{F}) ≥ 2^{−d}(3d)^{−3d} ≫ εV ≫ 1.

The last two formulae show that the number of facets of P is ≪ V ^{\frac{d−1}{d+1}} .

We mention that this implies, via a trick of Andrews, the following slightly stronger theorem whose proof can be found in [BL98].

THEOREM 10 For a lattice polytope P ∈ R^{d} with volume V > 0

T (P) ≪ V ^{\frac{d−1}{d+1}} .

7 Approximation

There are two types of problems in the theory of approximation of a K ∈ K by polytopes belonging to a certain class P of polytopes. The first type is asking for a lower bound, that is, a statement of the form: no polytope P ∈ P approximates K better than some function of K and P. The second is asking for the existence of a polytope P ∈ P which approximates K well, hopefully as well as the previous function. To be less vague, we consider inscribed polytopes only (that is P ⊂ K) and we measure approximation by the relative missed volume, that is, by

appr(K, P) = \frac{vol(K \ P)}{vol K}.

C. Schütt [Schü99] has recently proved two very neat and general results of the second type.

THEOREM 11 Given K ∈ K_{1} and t ∈ (0, t_{0}] (where t_{0} depends only on the dimension), there is a polytope P with K(v ≥ t) ⊂ P ⊂ K for which

f_{0}(P) ≪ \frac{vol K(t)}{t}.

THEOREM 12 Given K ∈ K_{1} and t ∈ (0, t_{0}] (where t_{0} depends only on the dimension), there is a polytope P with K(v ≥ t) ⊂ P ⊂ K for which

f_{d−1}(P) ≪ \frac{vol K(t)}{t}.

This means that appr(K, P) ≤ vol K(t) and the lost volume is “t per vertex”, and “t per facet”, respectively. We will see below that, for smooth bodies, this is the best possible order of magnitude. Schütt’s proof of these theorems is direct and somewhat lengthy. Here I present a simple argument showing the power and efficacy of the cap covering method. Nevertheless, this argument gives weaker constants than Schütt’s original theorem and does not extend to approximation by circumscribed polytopes (cf [Schü99]).

As the theorems are affinely invariant, we may assume that K is in standard position, i.e., it is sandwiched between two balls, both centered at the origin with the radius of the larger at most d times that of the smaller. For both theorems, start with setting τ = λt (where λ is a constant depending on d only) and choose a system of points {x_{1}, …, x_{m}} from bd K(v ≥ τ) maximal with respect to the property that the M(x_{i}, 1/2) are pairwise disjoint. The economic cap covering argument shows that

m ≪ \frac{vol K(τ)}{τ} ≪ \frac{vol K(t)}{t}.

We start with the case of the facets which is simpler. Fix λ = 6^{−d}. Let C(x_{i}) be a minimal cap, and define

P = K \ ∪_{1}^{m}C(x_{i})^{6}.

We will show that (1) no z ∈ bd K belongs to P, and (2) K(v ≥ t) ⊂ P. This clearly suffices for the facet case.

To see (1), assume z ∈ bd K, and let z^{∗} ∈ bd K(v ≥ τ) be the point on the segment connecting z and the origin (which is inside K(v ≥ τ) if t is small enough). Maximality implies the existence of i with M(z^{∗}, 1/2) ∩ M(x_{i}, 1/2) ≠ ∅, and by Lemma 1, M(z^{∗}, 1) ⊂ M(x_{i}, 5). It is easy to see, using the standard position of K, that z ∈ M(z^{∗}, 1), and so

z ∈ M(z^{∗}, 1) ⊂ M(x_{i}, 5) ⊂ C(x_{i})^{6}.

To check that (2) also holds, we write

vol C(x_{i})^{6} ≤ 6^{d} vol C(x_{i}) = 6^{d}τ = t,

so u(x) ≤ t for every point x cut off from K by one of the caps C(x_{i})^{6}.

For the proof of the vertex case set λ = d^{−1}6^{−d}. Let y_{i} be the intersection, with bd K, of the halfline through x_{i} starting from the origin, and define

P = conv{y_{1}, y_{2}, …, y_{m}}.

Clearly P ⊂ K. So we have to show K(v ≥ t) ⊂ P. Assume the contrary, then there is a halfspace H_{1} with P ∩ H_{1} = ∅ whose bounding hyperplane is tangent to K(v ≥ t). Note that no y_{i} is in H_{1}. Let H_{2} be the halfspace whose bounding hyperplane is parallel to that of H_{1}, and which is tangent to K(v ≥ τ) at the point z. Set C_{j} = K ∩ H_{j}, j = 1, 2. Lemma 8 says that vol C_{2} ≤ dτ.

By the maximality of the x_{i}, M(z, 1/2) intersects some M(x_{i}, 1/2) and so

y_{i} ∈ M(x_{i}, 1) ⊂ M(z, 5).

Here y_{i} ∈ M(x_{i}, 1) follows from the standard position of K. It is not hard to see that the cap C_{2}^{6} contains M(z, 5). Further, the cap C_{2}^{6} is contained in the cap C_{1} as their bounding hyperplanes are parallel and vol C_{1} ≥ t (by Lemma 8), while, by the same lemma, vol C_{2}^{6} ≤ 6^{d} vol C_{2} ≤ 6^{d}dτ = t. Thus y_{i} ∈ C_{1} ⊂ H_{1}. A contradiction.

Let’s turn now to the first type of approximation questions. We will consider here the family of all polytopes inscribed in K with at most n s– dimensional faces. Denote this class of polytopes by P_{n}(K, s). The usual question of approximation by inscribed polytopes with at most n vertices, the case P_{n}(K, 0) in our notation, is well understood see [Gru93]. Given a smooth enough convex body K, for every polytope in P_{n}(K, 0)

appr(K, P) ≤ c(d, K)n^{− \frac{2}{d−1}} (1 + o(1))

as n → ∞. In the other direction, there exist polytopes P in P_{n}(K, 0) with

appr(K, P) ≥ c(d, K)n^{− \frac{2}{d−1}} (1 + o(1))

Here even the constant, its dependence on K and d, is almost completely known. In the same paper Gruber proves an asymtotic formula for circumscribed polytopes with at most n facets, and in [Lu99], Ludwig gives exact asymptotic formulae for the unrestricted case with n vertices and n facets, respectively. (Approximation is measured as the relative volume of the symmetric difference of P and K.)

Is there a similar estimate for P_{n}(K, s) when 0 < s < d − 1? Or a weaker one, giving the order of magnitude of appr(K, P)? This unusual approximation question has come up in connection with the integer convex hull (cf [BL98]).

Again, M-regions and cap coverings are going to help. I present the basic ideas of the proof in the case when K = B^{d} the unit ball R^{d}: this extends without serious difficulty to convex bodies whose product curvature is separated from 0 and ∞. It should be mentioned that K. Böröczky Jr in [Bö99] has worked out several other cases of this type, for instance, inscribed, circumscribed, and unrestricted polytopes with at most n s-dimensional faces (again when 0 < s < d − 1). His approach is different: it is based on local quadratic approximation of the boundary and uses power diagrams.

THEOREM 13 For every polytope P ∈ P_{n}(B^{d}, s), and for large enough n.

appr(B^{d}, P) ≫ n^{− \frac{2}{d−1}} .

The proof below is based on an idea from [BL98] which is used there when s = d − 1. This particular case, when K = B^{d} was first proved by Rogers [Ro53].

We may suppose that

vol(B^{d} \ P) ≤ b_{1}n^{− \frac{2}{d−1}}

for any particular constant b_{1} of our choice ( b_{1} depending on d), as otherwise there is nothing to prove. We assume further that s ≥ 1.

Let F_{1}, …, F_{n} denote the s-dimensional faces of P and let z_{i} be the nearest point of F_{i} to the origin. The minimal cap C(z_{i}) has width h_{i}. It is not hard to check that F_{i} ⊂ C(z_{i}). Also, vol(C(z_{i}) \ P) ≥ \frac{1}{2} vol C(z_{i}). This means that vol C(z_{i}) must be small, and so h_{i} must be small. Consequently, vol C(z_{i}) ≈ hi^{\frac{d+1}{2}} , as a quick computation reveals. Thus we have

∑_{1}^{n} hi^{\frac{d+1}{2}} ≪ vol(B^{d} \ P) ≤ b_{1}n^{− \frac{2}{d−1}} .

Choose next a subsystem {x_{i_{1}}, …, x_{i_{m}}} from the x_{i} which is, as we got used to it by now, maximal with respect to the property that the M-regions M(x_{i_{j}}, 1/2) are pairwise disjoint. To have simple notation set z_{j} = x_{i_{j}}. By Lemma 1, every C(x_{i}) is contained in some M(z_{j}, 5). So writing V for the set of vertices of P we clearly have

V ⊂ ∪_{1}^{n}F_{i} ⊂ ∪_{1}^{n}C(z_{i}) ⊂ ∪_{1}^{m}M(z_{j}, 5).

Fix ρ = b_{2}n^{− \frac{1}{d−1}} , where b_{2} is to be defined later. We want to show that the set V +ρB^{d} covers at most half of S^{d−1} = bd B^{d}. We estimate the surface area of this set by that of S^{d−1} ∩ ∪_{1}^{m}(M(z_{j}, 5) + ρB^{d}), which is clearly

\begin{matrix}≪ & ∑_{1}^{m} (ρ + hj^{\frac{1}{2}} )^{d−1} = ∑_{j=1}^{m} ∑_{k=0}^{d−1} \binom{d−1}{k}hj^{\frac{k}{2}} ρ^{d−1−k} \\ = & ∑_{k=0}^{d−1} \binom{d−1}{k}ρ^{d−1−k} (∑_{1}^{m} hj^{\frac{k}{2}} ) \\ ≤ & ∑_{k=0}^{d−1} \binom{d−1}{k}ρ^{d−1−k}m (\frac{1}{m} ∑_{1}^{m} hk^{\frac{d+1}{2}} )^{\frac{k}{d+1}} \\ = & m (ρ + (\frac{1}{m} ∑_{1}^{m} hj^{\frac{d+1}{2}} )^{\frac{1}{d+1}} )^{d−1} , \end{matrix}

where we used the inequality between the kth and (d + 1)st means.

The last expression is smaller than half the surface area of S^{d−1} if the constants b_{1}, b_{2} are chosen suitably. Indeed, as m ≤ n,

ρ = b_{2}n^{− \frac{1}{d−1}} ≤ b_{2}m^{− \frac{1}{d−1}} ,

and since ∑_{j=1}^{m} hj^{\frac{d+1}{2}} ≤ b_{1}n^{− \frac{2}{d−1}} ,

(\frac{1}{m} ∑ hj^{\frac{d+1}{2}} )^{\frac{1}{d+1}} ≤ b1^{\frac{1}{d+1}} m^{− \frac{1}{d−1}} .

We just proved that V + ρB^{d} misses at least half of S^{d−1}. But then

S^{d−1} \ (V + \frac{ρ}{2}B^{d})

contains many pairwise disjoint caps of radius ρ/2. This is shown by a greedy algorithm: assume the centers y_{p} ∈ S^{d−1} \ (V + ρB^{d}) of these caps C_{p} have been chosen for p = 1, 2, …, q and the caps are pairwise disjoint. The caps with centers y_{p} and radius ρ cover at most

qρ^{d−1} vol S^{d−1}

of S^{d−1} (vol here is understood as (d − 1)-dimensional). So as long as this is smaller than the surface area of

S^{d−1} \ (V + ρB^{d}),

there is room to choose the next center y_{q+1}. The algorithm produces as many as ≫ ρ^{−(d−1)} ≫ n pairwise disjoint caps. They are all disjoint from P, so the volume missed by P is

∑ vol C_{p} ≫ nρ^{d+1} ≫ n^{− \frac{2}{d−1}} ,

finishing the proof of Theorem 13.

Let us finally return to the second question from the introduction whether the number of vertices of the integer convex hull conv(K ∩ ℤ^{d}) is close to vol K(v ≤ 2^{d}). As we saw in section 4, the interesting cases are polytopes and smooth bodies. Assuming K is a smooth convex body with large volume, Andrews’s theorem says that

f_{0}(conv(ℤ^{d} ∩ K)) ≪ (vol K)^{\frac{d+1}{d−1}} ≈ vol K(v ≤ 2^{d}).

So the upper bound is as expected from the introduction. In the other direction, the results of [BL98] show that, for instance, the integer convex hull of rB^{d} has asymptoticly as many vertices as predicted. Further, Theorem 13, combined with Theorem 4 from [BL98] shows that for all s and for large enough r

f_{s}(conv(ℤ^{d} ∩ rB^{d})) ≫ vol(rB^{d})^{\frac{d+1}{d−1}} .

This extends to other smooth convex bodies as well.

In the case of polytopes the prediction is correct, again. But the proof goes without the M-region technique, it is more number theoretic. The interested reader should consult [CHKM92] and [BHL92].

References

[AW91] F. Affentranger, J. A. Wieacker: On the convex hull of uniform random points in a simple d-polytope. Discrete Comp. Geom., 6 (1991), 291–305.

[An63] G. E. Andrews: A lower bound for the volumes of strictly convex bodies with many boundary points. Trans. AMS, 106 (1993), 270–279.

[Ar80] V. I. Arnol’d: Statistics of integral convex polytopes. (in Russian) Funk. Anal. Pril., 14 (1980), 1–3. English translation: Funct. Anal. Appl., 14 (1980), 79–84.

[Bá89] I. Bárány: Intrinsic volumes and f-vectors of random polytopes. Math. Annalen, 285 (1989), 671–699.

[Bá92] I. Bárány: Random polytopes in smooth convex bodies. Mathematika, 39 (1992), 81–92.

[BHL92] I. Bárány, R. Howe, L. Lovász: On integer points in polyhedra: a lower bound. Combinatorica, 12 (1992), 135–142.

[BL88] I. Bárány, D. G. Larman: Convex bodies, economic cap coverings, random polytopes. Mathematika, 35 (1998), 274–291.

[BL98] I. Bárány, D. G. Larman: The convex hull of the integer points in a large ball. Math. Annalen, 312 (1998), 167–181.

[BB93] I. Bárány, Ch. Buchta: Random polytopes in a convex polytope, independence of shape, and concentration of vertices. Math. Annalen, 297 (1993), 467–497.

[BV92] I. Bárány, A. M. Vershik: On the number of convex lattice polytopes. GAFA Journal, 12 (1992), 381-393.

[Bl23] W. Blaschke: Affine Differentialgeometrie. Springer, Berlin, 1923.

[Bö99] K. Böröczky, Jr: Polytopal approximation bounding the number of k-faces. to appear in J. Appr. Theory, (1999).

[BCP93] H. Brönnimann, B. Chazelle, J. Pach: How hard is half-space range searching? Discrete Comp. Geom., 10 (1993), 143–156.

[Ch89] B. Chazelle: Lower bounds on the complexity of polytope range searching. J. Am. Math. Soc., 2 (1989), 637-666.

[CHKM92] W. Cook, M. Hartmann, R. Kannan, C. McDiarmid: On integer points in polyhedra. Combinatorica, 12 (1992), 27–37.

[ELR70] G. Ewald, D. G. Larman, C. A. Rogers: The directions of the line segments and of the r-dimensional balls on the boundary of a convex body in Euclidean space. Mathematika, 17 (1970), 1–20.

[Gro74] H. Groemer: On the mean value of the volume of a random polytope in a convex set. Archiv Math., 25 (1997), 86–90.

[Gru83] P.M. Gruber: In most cases approximation is irregular. Rend. Circ. Mat. Torino, 41 (1983), 19–33.

[Gru93] P.M. Gruber: Asymptotic estimates for best and stepwise approximation of convex bodies II. Forum Math., 5 (1993), 521– 538.

[Iv76] B. A. Ivanov: Exceptional directions for a convex body. (in Russian), Mat. Zametki, 20 (1976), 365–371. English translation: Math. Notes 20 (1976), 763–765.

[Kl57] V. Klee: Research problem No.5. Bull. AMS, 62 (1957), 419.

[Kl69] V. Klee: Can the boundary of a d–dimensional convex body contain segment in all directions? Amer. Math. Monthly, 76 (1969), 408–410.

[KS84] S. B. Konyagin, K. A. Sevastyanov: Estimation of the number of vertices of a convex integral polyhedron in terms of its volume. (in Russian) Funk. Anal. Pril., 18 (1984), 13–15. English translation: Funct. Anal. Appl., 18 (1984), 11–13.

[Le98] K. Leichtweiss: Affine geometry of convex bodies. Barth, Heidelberg, 1998.

[Lu99] M. Ludwig: Asymptotic approximation of smooth convex bodies by general polytopes. to appear in Mathematika (1999).

[Ma52] A. M. Macbeath: A theorem on non-homogeneous lattices. Annals of Math., 56 (1952), 269–293.

[Mat93] J. Matoušek: Range searching with efficient hierarchical cuttings. Discrete Comp. Geom., 10 (1993), 157–182.

[RS63] A. Rényi, R. Sulanke: Über die konvexe Hülle von n zufällig gewählten Punkten. Z. Wahrsch. Verw. Geb., 2 (1963), 75-84.

[Ro53] C. A. Rogers: The volume of a polyhedron inscribed in a sphere. J. London Math. Soc., 28 (1953), 410–416.

[Schm85] W. Schmidt: Integral points on surfaces and curves. Monatshefte Math., 99 (1985), 45–82.

[Schn78] R. Schneider: Kinematic measures for sets of colliding convex bodies. Mathematika, 25 (1978), 1–12.

[Schn93] R. Schneider: Convex bodies: the Brunn-Minkowski theory. Encyclopedia Math. Appl. vol 44. Cambridge University Press, Cambridge, 1993.

[Schn99] R. Schneider: Convex bodies in exceptional relative positions. to appear in J. London Math. Soc., (1999).

[Schn98] R. Schneider: Measures in convex geometry. Rend. Istit. Mat. Univ. Trieste, Suppl., Vol XXIX, (1998), 215–265.

[Schü94] C. Schütt: Random polytopes and affine surface area. Math. Nachr., 170 (1994), 227–249.

[Schü99] C. Schütt: Floating bodies, illumination bodies, and polytopal approximation. in: K. M. Ball (ed.) Convex Geometric Analysis, Cambridge, Math. sci. Res. Inst. Publ. 43 (1999), 203–229.

[Wi78] J. A. Wieacker: Einige Probleme der polyedrische approximation. Diplomarbeit, Albert-Ludwigs-Universität, Freiburg im Breisgau, 1978.

[WW93] W. Weil, J. A. Wieacker: Stochastic geometry. In: Handbook of convex geometry, North-Holland, Amsterdam (1993), 1391– 1438.

[Za72] V. A. Zalgaller: k–dimensional directions singular for a convex body F in R^{n} (in Russian), Zapiski Sem. Leningrad., 27 (1972), 67–72. English translation: J. Soviet Math., 3 (1972), 437–441.