Constant Minkowskian width in terms of double normals

We extend the notion of a double normal of a convex body from smooth, strictly convex Minkowski planes to arbitrary two-dimensional real, normed, linear spaces in two different ways. Then, for both of these ways, we obtain the following characterization theorem: a convex body K in a Minkowski plane is of constant Minkowskian width iff every chord I of K splits K into two compact convex sets K₁ and K₂ such that I is a Minkowskian double normal of K₁ or K₂. Furthermore, the Euclidean version of this theorem yields a new characterization of d-dimensional Euclidean ball where d 3.     

Directed Projection Functions of Convex Bodies

For 1 ≤ i < j < d, a j-dimensional subspace L of and a convex body K in , we consider the projection K|L of K onto L. The directed projection function v _i,j (K;L,u) is defined to be the i-dimensional size of the part of K|L which is illuminated in direction u ∈ L. This involves the i-th surface area measure of K|L and is motivated by Groemer’s [17] notion of semi-girth of bodies in . It is well-known that centrally symmetric bodies are determined (up to translation) by their projection functions, we extend this by showing that an arbitrary body is determined by any one of its directed projection functions. We also obtain a corresponding stability result. Groemer [17] addressed the case i = 1, j = 2, d = 3. For j > 1, we then consider the average of v _1,j (K;L,u) over all spaces L containing u and investigate whether the resulting function determines K. We will find pairs (d,j) for which this is the case and some pairs for which it is false. The latter situation will be seen to be related to some classical results from number theory. We will also consider more general averages for the case of centrally symmetric bodies. The research of the first author was supported in part by NSF Grant DMS-9971202 and that of the second author by a grant from the Volkswagen Foundation.     

A deterministic view of random sampling and its use in geometry

The combination of divide-and-conquer and random sampling has proven very effective in the design of fast geometric algorithms. A flurry of efficient probabilistic algorithms have been recently discovered, based on this happy marriage. We show that all those algorithms can be derandomized with only polynomial overhead. In the process we establish results of independent interest concerning the covering of hypergraphs and we improve on various probabilistic bounds in geometric complexity. For example, givenn hyperplanes ind-space and any integerr large enough, we show how to compute, in polynomial time, a simplicial packing of sizeO(r ^d ) which coversd-space, each of whose simplices intersectsO(n/r) hyperplanes.Bernard Chazelle wishes to acknowledge the National Science Foundation for supporting this research in part under Grant CCR-8700917. Joel Friedman wishes to acknowledge the National Science Foundation for supporting this research in part under Grant CCR-8858788, and this Office of Naval Research under Grant N00014-87-K-0467.A preliminary version of this work has appeared in the proceedings of the 29th Annual IEEE Symposium on Foundations of Computer Science (1988). 539–549.     

On low-dimensional faces that high-dimensional polytopes must have

We prove that every five-dimensional polytope has a two-dimensional face which is a triangle or a quadrilateral. We state and discuss the following conjecture: For every integerk1 there is an integer f(k) such that everyd-polytope,df(k), has ak-dimensional face which is either a simplex or combinatorially isomorphic to thek-dimensional cube.We give some related results concerning facet-forming polytopes and tilings. For example, sharpening a result of Schulte [25] we prove that there is no face to face tiling of ⁵ with crosspolytopes.Supported in part by a BSF Grant and by I.H.E.S, Bures-Sur-Yvette.     

A Lower Bound for the Translative Kissing Numbers of Simplices

H (K) of a d-dimensional convex body K is the maximum number of mutually non-overlapping translates of K that can be arranged so that all touch K. In this paper we show that holds for any d-dimensional simplex (). We also prove similar inequalities for some, more general classes of convex bodies. Received May 18, 1998     

Reverse inequalities for zonoids and their application

We prove inequalities for mixed volumes of zonoids with isotropic generating measures. A special case is an inequality for zonoids that is reverse to the generalized Urysohn inequality, between mean width and another intrinsic volume; here the equality case characterizes parallelepipeds. We apply this to a question from stochastic geometry. It is known that among the stationary Poisson hyperplane processes of given positive intensity in n-dimensional Euclidean space, the ones with rotation invariant distribution are characterized by the fact that they yield, for k∈{2,…,n}, the maximal intensity of the intersection process of order k. We show that, if the kth intersection density is measured in an affine-invariant way, the processes of hyperplanes with only n fixed directions are characterized by a corresponding minimum property.     

Constructing a polytope to approximate a convex body

We develop an algorithm to construct a convex polytopeP withn vertices, contained in an arbitrary convex bodyK inR ^d , so that the ratio of the volumes |K/P|/|K| is dominated byc ·. d/n ^2/(d–1).Supported in part by the fund for the promotion of research in the Technion     

Highly saturated packings and reduced coverings

We introduce and study certain notions which might serve as substitutes for maximum density packings and minimum density coverings. A body is a compact connected set which is the closure of its interior. A packingP with congruent replicas of a bodyK isn-saturated if non–1 members of it can be replaced withn replicas ofK, and it is completely saturated if it isn-saturated for eachn1. Similarly, a coveringC with congruent replicas of a bodyK isn-reduced if non members of it can be replaced byn–1 replicas ofK without uncovering a portion of the space, and its is completely reduced if it isn-reduced for eachn1. We prove that every bodyK ind-dimensional Euclidean or hyperbolic space admits both ann-saturated packing and ann-reduced covering with replicas ofK. Under some assumptions onKE ^d (somewhat weaker than convexity), we prove the existence of completely saturated packings and completely reduced coverings, but in general, the problem of existence of completely saturated packings, and completely reduced coverings remains unsolved. Also, we investigate some problems related to the the densities ofn-saturated packings andn-reduced coverings. Among other things, we prove that there exists an upper bound for the density of ad+2-reduced covering ofE ^d with congruent balls, and we produce some density bounds for then-saturated packings andn-reduced coverings of the plane with congruent circles.     

Unique local determination of convex bodies

Barker and Larman asked the following. Let \({K' \subset {\mathbb{R}}^d}\) be a convex body, whose interior contains a given convex body \({K \subset {\mathbb{R}}^d}\), and let, for all supporting hyperplanes H of K, the (d ? 1)-volumes of the intersections \({K' \cap H}\) be given. Is K′ then uniquely determined? Yaskin and Zhang asked the analogous Question when, for all supporting hyperplanes H of K, the d-volumes of the “caps” cut off from K′ by H are given. We give local positive answers to both of these questions, for small C²-perturbations of K, provided the boundary of K is C₊². In both cases, (d ? 1)-volumes or d-volumes can be replaced by k-dimensional quermassintegrals for \({1 \le k \le d-1}\) or for \({1 \le k \le d}\), respectively. Moreover, in the first case we can admit, rather than hyperplane sections, sections by l-dimensional affine planes, where \({1 \le k \le l \le d-1}\). In fact, here not all l-dimensional affine subspaces are needed, but only a small subset of them (actually, a (d ? 1)-manifold), for unique local determination of K′.     

On neighborly families of convex bodies

A family of convex bodies in E^d is called neighborly if the intersection of every two of them is (d-1)-dimensional. In the present paper we prove that there is an infinite neighborly family of centrally symmetric convex bodies in E^d, d 3, such that every two of them are affinely equivalent (i.e., there is an affine transformation mapping one of them onto another), the bodies have large groups of affine automorphisms, and the volumes of the bodies are prescribed. We also prove that there is an infinite neighborly family of centrally symmetric convex bodies in E^d such that the bodies have large groups of symmetries. These two results are answers to a problem of B. Grünbaum (1963). We prove also that there exist arbitrarily large neighborly families of similar convex d-polytopes in E^d with prescribed diameters and with arbitrarily large groups of symmetries of the polytopes.     

On the vertex index of convex bodies

We introduce the vertex index, vein(K), of a given centrally symmetric convex body K⊂Rd, which, in a sense, measures how well K can be inscribed into a convex polytope with small number of vertices. This index is closely connected to the illumination parameter of a body, introduced earlier by the first named author, and, thus, related to the famous conjecture in Convex Geometry about covering of a d-dimensional body by d² smaller positively homothetic copies. We provide asymptotically sharp estimates (up to a logarithmic term) of this index in the general case. More precisely, we show that for every centrally symmetric convex body K⊂Rd one has

     

On the Simplest Inverse Problem for Sums of Sets in Several Dimensions

d -dimensional sets having the smallest cardinality of the sum set. Let be a finite d-dimensional set such that . If , then K consists of d parallel arithmetic progressions with the same common difference. We also establish the structure of K in the remaining cases . Received: February 5, 1996/Revised: November 20, 1997     

A characterization of the duality mapping for convex bodies

We characterize the duality of convex bodies in d-dimensional Euclidean vector space, viewed as a mapping from the space of convex bodies containing the origin in the interior into the same space. The question for such a characterization was posed by Vitali Milman. The property that the duality interchanges pairwise intersections and convex hulls of unions is sufficient for a characterization, up to a trivial exception and the composition with a linear transformation. Received: March 2007, Accepted: April 2007     

Optimal cubature formulas for tensor products of certain classes of functions

We study the problem of constructing an optimal formula of approximate integration along a d-dimensional parallelepiped. Our construction utilizes mean values along intersections of the integration domain with n hyperplanes of dimension (d−1), each of which is perpendicular to some coordinate axis. We find an optimal cubature formula of this type for two classes of functions. The first class controls the moduli of continuity with respect to all variables, whereas the second class is the intersection of certain periodic multivariate Sobolev classes. We prove that all node hyperplanes of the optimal formula in each case are perpendicular to a certain coordinate axis and are equally spaced and the weights are equal. For specific moduli of continuity and for sufficiently large n, the formula remains optimal for the first class among cubature formulas with arbitrary positions of hyperplanes.     

On a question of K. Bezdek and T. Odor on Γ-parallelotops

K. Bezdek and T. Odor proved the following statement in [1]: If a covering ofE ³ is a lattice packing of the convex compact bodyK with packing lattice Λ (K is a Λ-parallelotopes) then there exists such a 2-dimensional sublattice Λ′ of Λ which is covered by the set ∪(K+z∣z ∈ Λ′). (K ∪L(Λ′) is a Λ′-parallelotopes). We prove that the statement is not true in the case of the dimensionsn=6, 7, 8. Supported by Hung. Nat. Found for Sci. Research (OTKA) grant no. 1615 (1991).     

Sections and projections of homothetic convex bodies

For a pair of convex bodies K₁ and K₂ in Euclidean space , n ≥ 3, possibly unbounded, we show that K₁ is a translate of K₂ if either of the following conditions holds: (i) the orthogonal projections of K₁ on 2-dimensional planes are translates of the respective orthogonal projections of K₂, (ii) there are points p₁ ∈K₁ and p₂ ∈K₂ such that for every pair of parallel 2-dimensional planesL₁and L₂ through p₁ and p₂, respectively, the section K₁ ∩ L₁is a translate of K₂ ∩ L₂.     

Ak-extreme point is the limit ofk-exposed points

It is proved that the relative boundary of ak-dimensional intersection of a hyperplane and a compact convex body is contained in the closure of the union of all intersections of dimension lower thanp that the same convex body makes with different hyperplanes.     

Mean projections and finite packings of convex bodies

Consider the convex hullQ ofn non-overlapping translates of a convex bodyC inE ^d ,n be large. IfQ has minimali-dimensional projection, 1i<d then we prove thatQ is approximately a sphere.     

Cutting hyperplanes for divide-and-conquer

Givenn hyperplanes inE ^d, a (1/r)-cutting is a collection of simplices with disjoint interiors, which together coverE ^d and such that the interior of each simplex intersects at mostn/r hyperplanes. We present a deterministic algorithm for computing a (1/r)-cutting ofO(r ^d) size inO(nr ^d–1) time. If we require the incidences between the hyperplanes and the simplices of the cutting to be provided, then the algorithm is optimal. Our method is based on a hierarchical construction of cuttings, which also provides a simple optimal data structure for locating a point in an arrangement of hyperplanes. We mention several other applications of our result, e.g., counting segment intersections, Hopcroft's line/point incidence problem, linear programming in fixed dimension.This research was supported in part by the National Science Foundation under Grant CCR-9002352.     

The cross-section body, plane sections of convex bodies and approximation of convex bodies, I

For a convex body K ^d we investigate three associated bodies, its intersection body IK (for 0int K), cross-section body CK, and projection body IIK, which satisfy IKCKIIK. Conversely we prove CKconst₁(d)I(K–x) for some xint K, and IIKconst₂ (d)CK, for certain constants, the first constant being sharp. We estimate the maximal k-volume of sections of 1/2(K+(-K)) with k-planes parallel to a fixed k-plane by the analogous quantity for K; our inequality is, if only k is fixed, sharp. For L ^d a convex body, we take n random segments in L, and consider their Minkowski average D. We prove that, for V(L) fixed, the supremum of V(D) (with also nN arbitrary) is minimal for L an ellipsoid. This result implies the Petty projection inequality about max V((IIM)*), for M ^d a convex body, with V(M) fixed. We compare the volumes of projections of convex bodies and the volumes of the projections of their sections, and, dually, the volumes of sections of convex bodies and the volumes of sections of their circumscribed cylinders. For fixed n, the pth moments of V(D) (1p<) also are minimized, for V(L) fixed, by the ellipsoids. For k=2, the supremum (nN arbitrary) and the pth moment (n fixed) of V(D) are maximized for example by triangles, and, for L centrally symmetric, for example by parallelograms. Last we discuss some examples for cross-section bodies.Research (partially) supported by Hungarian National Foundation for Scientific Research, Grant No. 41.