Mean width of random polytopes in a reasonably smooth convex body

Let K be a convex body in and let X_n=(x₁,…,x_n) be a random sample of n independent points in K chosen according to the uniform distribution. The convex hull K_n of X_n is a random polytope in K, and we consider its mean width W(K_n). In this article, we assume that K has a rolling ball of radius >0. First, we extend the asymptotic formula for the expectation of W(K)−W(K_n) which was earlier known only in the case when ∂K has positive Gaussian curvature. In addition, we determine the order of magnitude of the variance of W(K_n), and prove the strong law of large numbers for W(K_n). We note that the strong law of large numbers for any quermassintegral of K was only known earlier for the case when ∂K has positive Gaussian curvature.     

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.     

Quermassintegrals of a random polytope in a convex body

Let K be a convex body in \mathbbRⁿ \mathbb{R}^n with volume |K| = 1 |K| = 1 . We choose N 3 n+1 N \geq n+1 points x₁,?, x_N x_1,\ldots, x_N independently and uniformly from K, and write C(x₁,?, x_N) C(x_1,\ldots, x_N) for their convex hull. Let f : \mathbbR⁺ ? \mathbbR⁺ f : \mathbb{R^+} \rightarrow \mathbb{R^+} be a continuous strictly increasing function and 0 ￡ i ￡ n-1 0 \leq i \leq n-1 . Then, the quantity¶¶E (K, N, f °W_i) = ò_K ?ò_K f[W_i(C(x₁, ?, x_N))]dx_N ?dx₁ E (K, N, f \circ W_{i}) = \int\limits_{K} \ldots \int\limits_{K} f[W_{i}(C(x_1, \ldots, x_N))]dx_{N} \ldots dx_1 ¶¶is minimal if K is a ball (W_i is the i-th quermassintegral of a compact convex set). If f is convex and strictly increasing and 1 ￡ i ￡ n-1 1 \leq i \leq n-1 , then the ball is the only extremal body. These two facts generalize a result of H. Groemer on moments of the volume of C(x₁,?, x_N) C(x_1,\ldots, x_N) .     

Limit theorems for the diameter of a random sample in the unit ball

We prove a limit theorem for the maximum interpoint distance (also called the diameter) for a sample of n i.i.d. points in the unit d-dimensional ball for d≥2. The results are specialised for the cases when the points have spherical symmetric distributions, in particular, are uniformly distributed in the whole ball and on its boundary. Among other examples, we also give results for distributions supported by pointed sets, such as a rhombus or a family of segments.      

High dimensional random sections of isotropic convex bodies

We study two properties of random high dimensional sections of convex bodies. In the first part of the paper we estimate the central section function for random F∈Gn,k and K⊂Rn a centrally symmetric isotropic convex body. This partially answers a question raised by V.D. Milman and A. Pajor (see [V.D. Milman, A. Pajor, Isotropic positions and inertia ellipsoids and zonoids of the unit ball of a normed n-dimensional space, in: Lecture Notes in Math., vol. 1376, Springer, 1989, p. 88]). In the second part we show that every symmetric convex body has random high dimensional sections F∈Gn,k with outer volume ratio bounded by

     

Large deviations for heavy-tailed random elements in convex cones

We prove large deviation results for sums of heavy-tailed random elements in rather general convex cones being semigroups equipped with a rescaling operation by positive real numbers. In difference to previous results for the cone of convex sets, our technique does not use the embedding of cones in linear spaces. Examples include the cone of convex sets with the Minkowski addition, positive half-line with maximum operation and the family of square integrable functions with arithmetic addition and argument rescaling.     

Distribution-independent properties of the convex hull of random points

Denote byV _n ^(d) the expected volume of the convex hull ofn points chosen independently according to a given probability measure in Euclideand-spaceE ^d. Ifd=2 ord=3 and is the measure corresponding to the uniform distribution on a convex body inE ^d, Affentranger and Badertscher derived that

On the average complexity of 3D-Voronoi diagrams of random points on convex polytopes

It is well known that the complexity, i.e. the number of vertices, edges and faces, of the 3-dimensional Voronoi diagram of n points can be as bad as Θ(n²). It is also known that if the points are chosen Independently Identically Distributed uniformly from a 3-dimensional region such as a cube or sphere, then the expected complexity falls to O(n). In this paper we introduce the problem of analyzing what occurs if the points are chosen from a 2-dimensional region in 3-dimensional space. As an example, we examine the situation when the points are drawn from a Poisson distribution with rate n on the surface of a convex polytope. We prove that, in this case, the expected complexity of the resulting Voronoi diagram is O(n).     

New bounds on the average distance from the Fermat–Weber center of a planar convex body

The Fermat–Weber center of a planar body Q is a point in the plane from which the average distance to the points in Q is minimal. We first show that for any convex body Q in the plane, the average distance from the Fermat–Weber center of Q to the points in Q is larger than , where Δ(Q) is the diameter of Q. This proves a conjecture of Carmi, Har-Peled and Katz. From the other direction, we prove that the same average distance is at most . The new bound substantially improves the previous bound of due to Abu-Affash and Katz, and brings us closer to the conjectured value of . We also confirm the upper bound conjecture for centrally symmetric planar convex bodies.     

Bodies of constant width in arbitrary dimension

We give a number of characterizations of bodies of constant width in arbitrary dimension. As an application, we describe a way to construct a body of constant width in dimension n, one of its (n – 1)‐dimensional projection being given. We give a number of examples, like a four‐dimensional body of constant width whose 3D‐projection is the classical Meissner's body. (© 2007 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

The expected number of extreme points of a random linear program

There has been increasing attention recently on average case algorithmic performance measures since worst case measures can be qualitatively quite different. An important characteristic of a linear program, relating to Simplex Method performance, is the number of vertices of the feasible region. We show 2 ⁿ to be an upper bound on the mean number of extreme points of a randomly generated feasible region with arbitrary probability distributions on the constraint matrix and right hand side vector. The only assumption made is that inequality directions are chosen independently in accordance with a series of independent fair coin tosses.We would like to thank the Institute of Pure and Applied Mathematics in Rio de Janeiro for supporting the authors' collaboration that led to this paper.     

On the shape of a convex body with respect to its second projection body

We prove results relative to the problem of finding sharp bounds for the affine invariant $P(K)=V(\mathrm{\Pi }K)/V^{d-1}(K)$. Namely, we prove that if K is a 3-dimensional zonoid of volume 1, then its second projection body ${\mathrm{\Pi }}^{2}K$ is contained in 8K, while if K is any symmetric 3-dimensional convex body of volume 1, then ${\mathrm{\Pi }}^{2}K$ contains 6K. Both inclusions are sharp. Consequences of these results include a stronger version of a reverse isoperimetric inequality for 3-dimensional zonoids established by the author in a previous work, a reduction for the 3-dimensional Petty conjecture to another isoperimetric problem and the best known lower bound up to date for $P(K)$ in 3 dimensions. As byproduct of our methods, we establish an almost optimal lower bound for high-dimensional bodies of revolution.     

Transversal numbers of translates of a convex body

Let F be a family of translates of a fixed convex set M in Rⁿ. Let τ(F) and ν(F) denote the transversal number and the independence number of F, respectively. We show that ν(F)?τ(F)?8ν(F)-5 for n=2 and τ(F)?2^n-1nⁿν(F) for n?3. Furthermore, if M is centrally symmetric convex body in the plane, then ν(F)?τ(F)?6ν(F)-3.     

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.     

Topology of the hyperspace of convex bodies of constant width

The hyperspace of all convex bodies of constant width in Euclidean spaceR ⁿ ,n≥2, is proved to be homeomorphic to a contractibleQ-manifold (Q denotes the Hilbert cube). The proof makes use of an explicitly constructed retraction of the entire hyperspace of convex bodies on the hyperspace of convex bodies of constant width. Translated fromMaternaticheskie Zametki, Vol. 62, No. 6, pp. 813–819, December, 1997 Translated by V. N. Dubrovsky