Hadwiger's covering conjecture and low dimensional dual cyclic polytopes

LetK be a convex body in a Euclideand-spaceE ^d withd1. In 1957, H. Hadwiger conjectured thatK can always be covered by 2 ^d smaller homothetic copies ofK. We verify this conjecture in the case thatK is the polar of a cyclicd-polytope andd=3, 4 and 5.     

Konstruktion regulärer Hüllen konstanter Breite

LetM be a compact, convex set of diameter 2 inE ^d. There exists a bodyK of constant width 2 containingM such that every symmetry ofM is one ofK and every singular boundary point ofK is a boundary point ofM, for which the set of antipodes inK is the convex hull of the antipodes, which are already inM.

---

---

Mit 1 Abbildung     

Reduced convex bodies in Euclidean space—A survey

A convex body R in Euclidean space E^d is called reduced if the minimal width Δ(K) of each convex body K⊂R different from R is smaller than Δ(R). This definition yields a class of convex bodies which contains the class of complete sets, i.e., the family of bodies of constant width. Other obvious examples in E² are regular odd-gons. We know a relatively large amount on reduced convex bodies in E². Besides theorems which permit us to understand the shape of their boundaries, we have estimates of the diameter, perimeter and area. For d≥3 we do not even have tools which permit us to recognize what the boundary of R looks like. The class of reduced convex bodies has interesting applications. We present the current state of knowledge about reduced convex bodies in E^d, recall some striking related research problems, and put a few new questions.     

On two finite covering problems of Bambah,Rogers, Woods and Zassenhaus

Bambah, Rogers, Woods, and Zassenhaus considered the general problem of covering planar convex bodiesC byk translates of a centrally-symmetric convex bodyK ofE ² with the ramification that these translates cover the convex hullC _k of their centres. They proved interesting inequalities for the volume ofC andC _k . In the present paper some analogous results in euclideand-spaceE ^d are given. It turns out that on one hand extremal configurations ford5 are of quite different type than in the planar case. On the other hand inequalities similar to the planar ones seem to exist in general. Inequalities in both directions for the volume and other quermass-integrals are given.     

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.     

Polar factorization and monotone rearrangement of vector-valued functions

Given a probability space (X, μ) and a bounded domain Ω in ?^d equipped with the Lebesgue measure |·| (normalized so that |Ω| = 1), it is shown (under additional technical assumptions on X and Ω) that for every vector-valued function u ∈ L^p (X, μ; ?^d) there is a unique “polar factorization” u = ?Ψs, where Ψ is a convex function defined on Ω and s is a measure-preserving mapping from (X, μ) into (Ω, |·|), provided that u is nondegenerate, in the sense that μ(u^?1(E)) = 0 for each Lebesgue negligible subset E of ?^d. Through this result, the concepts of polar factorization of real matrices, Helmholtz decomposition of vector fields, and nondecreasing rearrangements of real-valued functions are unified. The Monge-Ampère equation is involved in the polar factorization and the proof relies on the study of an appropriate “Monge-Kantorovich” problem.     

Tiling convex sets by translates

LetK be a compact, convex subset ofE ^dwhich can be tiled by a finite number of disjoint (on interiors) translates of some compact setY. Then we may writeK=X+Y, whereX is finite. The possible structures forK, X andY are completely determined under these conditions.     

The chance that a convex body is lattice‐point free: A relative of Buffon's needle problem

Given a convex body K ⊂ R ^d, what is the probability that a randomly chosen congruent copy, K^*, of K is lattice‐point free, that is, K^*∩ Z ^d = ∅︁? Here Z ^d is the usual lattice of integer points in R ^d. Luckily, the underlying probability is well defined since integer translations of K can be factored out. The question came up in connection with integer programming. We explain what the answer is for convex bodies of large enough volume. © 2006 Wiley Periodicals, Inc. Random Struct. Alg., 2007     

The space of compact subsets of E d

Let K be the space of compact subsets of E ^d, endowed with the Hausdorff-metric. It is shown that the isometries of K onto itself are the mappings generated by rigid motions of E ^d.     

The generic contact of convex bodies with circumscribed homothets of a convex surface

LetS ₀ be a convex surface ind-dimensional Euclidean spaceE ^d . Then, ifS ₀ is smooth and strictly convex, we prove that the typical convex body touches the convex suface circumscribed about it and homothetic toS ₀ at preciselyd+1 points.     

On combinatorial and affine automorphisms of polytopes

We disprove the longstanding conjecture that every combinatorial automorphism of the boundary complex of a convex polytope in euclidean spaceE ^d can be realised by an affine transformation ofE ^d .     

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     

On the expected number of k-sets

Given a setS ofn points inR ^d , a subsetX of sized is called ak-simplex if the hyperplane aff(X) has exactlyk points on one side. We studyE _d (k,n), the expected number of k-simplices whenS is a random sample ofn points from a probability distributionP onR ^d . WhenP is spherically symmetric we prove thatE _d (k, n)≤cn ^d−1 WhenP is uniform on a convex bodyK⊂R ² we prove thatE ₂ (k, n) is asymptotically linear in the rangecn≤k≤n/2 and whenk is constant it is asymptotically the expected number of vertices on the convex hull ofS. Finally, we construct a distributionP onR ² for whichE ₂((n−2)/2,n) iscn logn. The authors express gratitude to the NSF DIMACS Center at Rutgers and Princeton. The research of I. Bárány was supported in part by Hungarian National Science Foundation Grants 1907 and 1909, and W. Steiger's research was supported in part by NSF Grants CCR-8902522 and CCR-9111491.     

Zur Analytischen Darstellung des Ranges Konvexer Körper Durch Stützhyperboloide

LetK be a convex body in (n+1)-dimensional Euclidean space Eⁿ⁺¹. The set (K) of all support-elements ofK is uniquely determined by the semiaxis-function a(u). First part of this note contains an explicit specification of the support-elements by means of a(u), and in the second part we give necessary and sufficient conditions which characterize a function a(u) as semiaxis-function of a closed convex subset of Eⁿ⁺¹.     

Tame linear extension operators for smooth Whitney functions

For a compact set K⊆Rd we present a rather easy construction of a linear extension operator E:E(K)→C^∞(Rd) for the space of Whitney jets E(K) which satisfies linear tame continuity estimates , where ‖⋅s_‖ denotes the s-th Whitney norm. The construction turns out to be possible if and only if the local Markov inequality LMI(s) introduced by Bos and Milman holds for every s>r on K. In particular, E(K) admits a tame linear extension operator if and only if the local Markov inequality LMI(s) holds on K for some s?1.     

On Grünbaum's Conjecture about Inner Illumination of Convex Bodies

In 1964 Grünbaum conjectured that any primitive set illuminating from within a convex body in E ^d , d ≥ 3 , has at most 2 ^d points. This was confirmed by V. Soltan in 1995 for the case d = 3 . Here we give a negative answer to Grünbaum's conjecture for all d ≥ 4 , by constructing a convex body K ⊂ E ^d with primitive illuminating sets of an arbitrarily large cardinality. Received December 1, 1997, and in revised form January 21, 1999.     

On-line covering a cube by a sequence of cubes

A procedure for packing or covering a given convex bodyK with a sequence of convex bodies {C _i} is anon-line method if the setC _i are given in sequence. andC _i+1 is presented only afterC _i has been put in place, without the option of changing the placement afterward. The “one-line” idea was introduced by Lassak and Zhang [6] who found an asymptotic volume bound for the problem of on-line packing a cube with a sequence of convex bodies. In this note a problem of Lassak is solved, concerning on-line covering a cube with a sequence of cubes, by proving that every sequence of cubes in the Euclidean spaceE ^d whose total volume is greater than 4 ^d admits an on-line covering of the unit cube. Without the “on-line” restriction, the best possible volume bound is known to be 2 ^d −1, obtained by Groemer [2] and, independently, by Bezdek and Bezdek [1]. The on-line covering method described in this note is based on a suitable cube-filling Peano curve.     

On pyramids and reducedness

A convex body K in ℝ ^d is said to be reduced if the minimum width of each convex body properly contained in K is strictly smaller than the minimum width of K. We study the question of Lassak on the existence of reduced polytopes of dimension larger than two. We show that a pyramid of dimension larger than two with equal numbers of facets and vertices is not reduced. This generalizes the main result from [8].      

The expected value of some functions of the convex hull of a random set of points sampled inR d

This paper presents formulas and asymptotic expansions for the expected number of vertices and the expected volume of the convex hull of a sample ofn points taken from the uniform distribution on ad-dimensional ball. It is shown that the expected number of vertices is asymptotically proportional ton ^{(d−1)/(d+1)}, which generalizes Rényi and Sulanke’s asymptotic raten ^(1/3) ford=2 and agrees with Raynaud’s asymptotic raten ^{(d−1)/(d+1)} for the expected number of facets, as it should be, by Bárány’s result that the expected number ofs-dimensional faces has order of magnitude independent ofs. Our formulas agree with the ones Efron obtained ford=2 and 3 under more general distributions. An application is given to the estimation of the probability content of an unknown convex subset ofR ^d .     

Lower Bounds for Dimensions of Sums of Sets

We study lower bounds for the Minkowski and Hausdorff dimensions of the algebraic sum E+K of two sets E,K⊂ℝ ^d .