Sylvester’s Problem for Symmetric Convex Bodies and Related Problems

We consider moments of the normalized volume of a symmetric or nonsymmetric random polytope in a fixed symmetric convex body. We investigate for which bodies these moments are extremized, and calculate exact values in some of the extreme cases. We show that these moments are maximized among planar convex bodies by parallelograms.     

Sylvester’s Problem for Symmetric Convex Bodies and Related Problems

We consider moments of the normalized volume of a symmetric or nonsymmetric random polytope in a fixed symmetric convex body. We investigate for which bodies these moments are extremized, and calculate exact values in some of the extreme cases. We show that these moments are maximized among planar convex bodies by parallelograms.     

The parallel volume at large distances

In this paper we examine the asymptotic behavior of the parallel volume of planar non-convex bodies as the distance tends to infinity. We show that the difference between the parallel volume of the convex hull of a body and the parallel volume of the body itself tends to 0. This yields a new proof for the fact that a planar body can only have polynomial parallel volume if it is convex. Extensions to Minkowski spaces and random sets are also discussed.     

On the variance of random polytopes

A random polytope is the convex hull of uniformly distributed random points in a convex body K. A general lower bound on the variance of the volume and f-vector of random polytopes is proved. Also an upper bound in the case when K is a polytope is given. For polytopes, as for smooth convex bodies, the upper and lower bounds are of the same order of magnitude. The results imply a law of large numbers for the volume and f-vector of random polytopes when K is a polytope.     

Dispersion of mass and the complexity of randomized geometric algorithms

How much can randomness help computation? Motivated by this general question and by volume computation, one of the few instances where randomness provably helps, we analyze a notion of dispersion and connect it to asymptotic convex geometry. We obtain a nearly quadratic lower bound on the complexity of randomized volume algorithms for convex bodies in Rn (the current best algorithm has complexity roughly n⁴, conjectured to be n³). Our main tools, dispersion of random determinants and dispersion of the length of a random point from a convex body, are of independent interest and applicable more generally; in particular, the latter is closely related to the variance hypothesis from convex geometry. This geometric dispersion also leads to lower bounds for matrix problems and property testing.     

Moment inequalities and central limit properties of isotropic convex bodies

The object of our investigations are isotropic convex bodies , centred at the origin and normed to volume one, in arbitrary dimensions. We show that a certain subset of these bodies – specified by bounds on the second and fourth moments – is invariant under forming ‘expanded joinsrsquo;. Considering a body K as above as a probability space and taking , we define random variables on K. It is known that for subclasses of isotropic convex bodies satisfying a ‘concentration of mass property’, the distributions of these random variables are close to Gaussian distributions, for high dimensions n and ‘most’ directions . We show that this ‘central limit property’, which is known to hold with respect to convergence in law, is also true with respect to -convergence and -convergence of the corresponding densities. Received: 21 March 2001 / in final form: 17 October 2001 / Published online: 4 April 2002     

Reverse Brunn–Minkowski and reverse entropy power inequalities for convex measures

We develop a reverse entropy power inequality for convex measures, which may be seen as an affine-geometric inverse of the entropy power inequality of Shannon and Stam. The specialization of this inequality to log-concave measures may be seen as a version of Milman?s reverse Brunn–Minkowski inequality. The proof relies on a demonstration of new relationships between the entropy of high dimensional random vectors and the volume of convex bodies, and on a study of effective supports of convex measures, both of which are of independent interest, as well as on Milman?s deep technology of M-ellipsoids and on certain information-theoretic inequalities. As a by-product, we also give a continuous analogue of some Plünnecke–Ruzsa inequalities from additive combinatorics.     

John's Decomposition of the Identity in the Non-Convex Case

We prove an extension of the classical John's Theorem, that characterises the ellipsoid of maximal volume position inside a convex body by the existence of some kind of decomposition of the identity, obtaining some results for maximal volume position of a compact and connected set inside a convex set with nonempty interior. By using those results we give some estimates for the outer volume ratio of bodies not necessarily convex.     

Small-Ball Probabilities for the Volume of Random Convex Sets

We prove small-deviation estimates for the volume of random convex sets. The focus is on convex hulls and Minkowski sums of line segments generated by independent random points. The random models considered include (Lebesgue) absolutely continuous probability measures with bounded densities and the class of log-concave measures.     

On determinants and the volume of random polytopes in isotropic convex bodies

In this paper we consider random polytopes generated by sampling points in multiple convex bodies. We prove related estimates for random determinants and give applications to several geometric inequalities.     

Volumes of symmetric random polytopes

We consider the moments of the volume of the symmetric convex hull of independent random points in an n-dimensional symmetric convex body. We calculate explicitly the second and fourth moments for n points when the given body is (and all of the moments for the case q = 2), and derive from these the asymptotic behavior, as , of the expected volume of a random simplex in those bodies. Received: 5 February 2003     

On a normed version of a Rogers–Shephard type problem

A translation body of a convex body is the convex hull of two of its translates intersecting each other. In the 1950s, Rogers and Shephard found the extremal values, over the family of n-dimensional convex bodies, of the maximal volume of the translation bodies of a given convex body. In our paper, we introduce a normed version of this problem, and for the planar case, determine the corresponding quantities for the four types of volumes regularly used in the literature: Busemann, Holmes–Thompson, and Gromov’s mass and mass*. We examine the problem also for higher dimensions, and for centrally symmetric convex bodies.     

Random walks in a convex body and an improved volume algorithm

We give a randomized algorithm using O(n⁷ log² n) separation calls to approximate the volume of a convex body with a fixed relative error. The bound is O(n⁶ log⁴ n) for centrally symmpetric bodies and for polytopes with a polynomial number of facets, and O(n⁵ log⁴ n) for centrally symmetric polytopes with a polynomial number of facets. We also give an O(n⁶ log n) algorithm to sample a point from the uniform distribution over a convex body. Several tools are developed that may be interesting on their own. We extend results of Sinclair–Jerrum [43] and the authors [34] on the mixing rate of Markov chains from finite to arbitrary Markov chains. We also analyze the mixing rate of various random walks on convex bodies, in particular the random walk with steps from the uniform distribution over a unit ball. © 1993 John Wiley & Sons, Inc.     

Multidimensional Hermite-Hadamard inequalities and the convex order

The problem of establishing inequalities of the Hermite-Hadamard type for convex functions on n-dimensional convex bodies translates into the problem of finding appropriate majorants of the involved random vector for the usual convex order. We present two results of partial generality which unify and extend the most part of the multidimensional Hermite-Hadamard inequalities existing in the literature, at the same time that lead to new specific results. The first one fairly applies to the most familiar kinds of polytopes. The second one applies to symmetric random vectors taking values in a closed ball for a given (but arbitrary) norm on Rn. Related questions, such as estimates of approximation and extensions to signed measures, also are briefly discussed.     

Asymptotic Shapes of large Cells in Random Tessellations

We establish a close relationship between isoperimetric inequalities for convex bodies and asymptotic shapes of large random polytopes, which arise as cells in certain random mosaics in d-dimensional Euclidean space. These mosaics are generated by Poisson hyperplane processes satisfying a few natural assumptions (not necessarily stationarity or isotropy). The size of large cells is measured by a class of general functionals. The main result implies that the asymptotic shapes of large cells are completely determined by the extremal bodies of an inequality of isoperimetric type, which connects the size functional and the expected number of hyperplanes of the generating process hitting a given convex body. We obtain exponential estimates for the conditional probability of large deviations of zero cells from asymptotic or limit shapes, under the condition that the cells have large size. This work was supported in part by the European Network PHD, FP6 Marie Curie Actions, RTN, Contract MCRN-511953. Received: May 2005 Accepted: September 2005     

Minimal volume product near Hanner polytopes

Mahler?s conjecture asks whether the cube is a minimizer for the volume product of a body and its polar in the class of symmetric convex bodies in a fixed dimension. It is known that every Hanner polytope has the same volume product as the cube or the cross-polytope. In this paper we prove that every Hanner polytope is a strict local minimizer for the volume product in the class of symmetric convex bodies endowed with the Banach–Mazur distance.     

Error of Asymptotic Formulae for Volume Approximation of Convex Bodies in

 We estimate the error of asymptotic formulae for volume approximation of sufficiently differentiable convex bodies by circumscribed convex polytopes as the number of facets tends to infinity. Similar estimates hold for approximation with inscribed and general polytopes and for vertices instead of facets. Our result is then applied to estimate the minimum isoperimetric quotient of convex polytopes as the number of facets tends to infinity.     

Convolutions, Transforms, and Convex Bodies

The paper studies convex bodies and star bodies in Rⁿ by usingRadon transforms on Grassmann manifolds, p-cosine transformson the unit sphere, and convolutions on the rotation group ofRⁿ. It presents dual mixed volume characterizations of i-intersectionbodies and L_p-balls which are related to certain volume inequalitiesfor cross sections of convex bodies. It considers approximationsof special convex bodies by analytic bodies and various finitesums of ellipsoids which preserve special geometric properties.Convolution techniques are used to derive formulas for mixedvolumes, mixed surface measures, and p-cosine transforms. Theyare also used to prove characterizations of geometric functionals,such as surface area and dual quermassintegrals. 1991 MathematicsSubject Classification: 52A20, 52A40.     

Fuchsian convex bodies: basics of Brunn–Minkowski theory

The hyperbolic space ${\mathbb{H}^d}$ can be defined as a pseudo-sphere in the (d + 1) Minkowski space-time. In this paper, a Fuchsian group Γ is a group of linear isometries of the Minkowski space such that ${\mathbb{H}^d/\Gamma}$ is a compact manifold. We introduce Fuchsian convex bodies, which are closed convex sets in Minkowski space, globally invariant for the action of a Fuchsian group. A volume can be associated to each Fuchsian convex body, and, if the group is fixed, Minkowski addition behaves well. Then Fuchsian convex bodies can be studied in the same manner as convex bodies of Euclidean space in the classical Brunn–Minkowski theory. For example, support functions can be defined, as functions on a compact hyperbolic manifold instead of the sphere. The main result is the convexity of the associated volume (it is log concave in the classical setting). This implies analogs of Alexandrov–Fenchel and Brunn–Minkowski inequalities. Here the inequalities are reversed.     

A note on volume thresholds for random polytopes

Geometriae Dedicata - We study the expected volume of random polytopes generated by taking the convex hull of independent identically distributed points from a given distribution. We show that, for...