On the volume of convex hulls of sets on spheres

We prove that for a measurable subset of S ^n–1 with fixed Haar measure, the volume of its convex hull is minimized for a cap (i.e. a ball with respect to the geodesic measure). We solve a similar problem for symmetric sets and n=2, 3. As a consequence, we deduce a result concerning Gaussian measures of dilatations of convex, symmetric sets in R ² and R ³.Partially supported by KBN (Poland), Grant No. 2 1094 91 01.     

Characterization off-vectors of families of convex sets inR d Part I: Necessity of Eckhoff’s conditions

LetK=K ₁,...,K_n be a family ofn convex sets inR ^d . For 0≦i<n denote byf _i the number of subfamilies ofK of sizei+1 with non-empty intersection. The vectorf(K) is called thef-vectors ofK. In 1973 Eckhoff proposed a characterization of the set off-vectors of finite families of convex sets inR ^d by a system of inequalities. Here we prove the necessity of Eckhoff's inequalities. The proof uses exterior algebra techniques. We introduce a notion of generalized homology groups for simplicial complexes. These groups play a crucial role in the proof, and may be of some independent interest.     

Bounded linear regularity of convex sets in Banach spaces and its applications

This paper deals with bounded linear regularity, linear regularity and the strong conical hull intersection property (CHIP) of a collection of finitely many closed convex intersecting sets in Banach spaces. It is shown that, as in finite dimensional space setting (see [6]), the standard constraint qualification implies bounded linear regularity, which in turn yields the strong conical hull intersection property, and that the collection of closed convex sets {C ₁, . . . ,C _n } is bounded linearly regular if and only if the tangent cones of {C ₁, . . . ,C _n } has the CHIP and the normal cones of {C ₁, . . . ,C _n } has the property (G)(uniformly on a neighborhood in the intersection C). As applications, we study the global error bounds for systems of linear and convex inequalities. The work of this author was partially supported by the National Natural Sciences Grant (No. 10471032) and the Excellent Young Teachers Program of MOE, P.R.C The authors thank professor K.F.Ng for his helpful discussion and the referee for their helpful suggestions on improving the first version of this paper     

Compact,convex sets in R n and a new banach lattice. I.- Theory.

The present paper shows that compact, non-empty convex sets in R ⁿ form a wedge in a well-defined Banach lattice, which turns out to be isometrically Riesz-isomorphic to the continuous functions in S ^n–1, the unit sphere of R ⁿ . Among other results, we obtain Dini-like convergence results for sets, linking order- and norm-convergence.     

Lattice coverings and Gaussian measures of n-dimensional convex bodies

Let be the euclidean norm on R ⁿ and let γ _n be the (standard) Gaussian measure on R ⁿ with density . Let be defined by and let L be a lattice in R ⁿ generated by vectors of norm ≤ϑ. Then, for any closed convex set V in R ⁿ with , we have (equivalently, for any . The above statement can also be viewed as a ``nonsymmetric' version of the Minkowski theorem. Received March 6, 1995, and in revised form January 26, 1996.     

Illuminating high-dimensional convex sets

A setL of points in thed-spaceE ^d is said toilluminate a familyF={S ₁, ...,S _n } ofn disjoint compact sets inE ^d if for every setS _i inF and every pointx in the boundary ofS _i there is a pointv inL such thatv illuminatesx, i.e. the line segment joiningv tox intersects the union of the elements ofF in exactly {x}.The problem we treat is the size of a setS needed to illuminate a familyF={S ₁, ...,S _n } ofn disjoint compact sets inE ^d . We also treat the problem of putting these convex sets in mutually disjoint convex polytopes, each one having at most a certain number of facets.     

Intersection patterns of convex sets

LetK ₁,…K_n be convex sets inR ^d. For 0≦i denote byf _ithe number of subsetsS of {1,2,…,n} of cardinalityi+1 that satisfy ∩{K _i∶i∈S}≠Ø. We prove:Theorem.If f _d+r=0 for somer r>=0, then {fx161-1} This inequality was conjectured by Katchalski and Perles. Equality holds, e.g., ifK ₁=…=K_r=R^d andK _r+1,…,K_n aren?r hyperplanes in general position inR ^d. The proof uses multilinear techniques (exterior algebra). Applications to convexity and to extremal set theory are given.     

Minimization of convex functions on the convex hull of a point set

A basic algorithm for the minimization of a differentiable convex function (in particular, a strictly convex quadratic function) defined on the convex hull of m points in R ⁿ is outlined. Each iteration of the algorithm is implemented in barycentric coordinates, the number of which is equal to m. The method is based on a new procedure for finding the projection of the gradient of the objective function onto a simplicial cone in R ^m , which is the tangent cone at the current point to the simplex defined by the usual constraints on barycentric coordinates. It is shown that this projection can be computed in O(m log m) operations. For strictly convex quadratic functions, the basic method can be refined to a noniterative method terminating with the optimal solution.     

On convex optimization without convex representation

We consider the convex optimization problem P:min_x {f(x) : x ? K}{{\rm {\bf P}}:{\rm min}_{\rm {\bf x}} \{f({\rm {\bf x}})\,:\,{\rm {\bf x}}\in{\rm {\bf K}}\}} where f is convex continuously differentiable, and K ì \mathbb Rⁿ{{\rm {\bf K}}\subset{\mathbb R}^n} is a compact convex set with representation {x ? \mathbb Rⁿ : g_j(x) 3 0, j = 1,?,m}{\{{\rm {\bf x}}\in{\mathbb R}^n\,:\,g_j({\rm {\bf x}})\geq0, j = 1,\ldots,m\}} for some continuously differentiable functions (g _j ). We discuss the case where the g _j ’s are not all concave (in contrast with convex programming where they all are). In particular, even if the g _j are not concave, we consider the log-barrier function f_m{\phi_\mu} with parameter μ, associated with P, usually defined for concave functions (g _j ). We then show that any limit point of any sequence (x_m) ì K{({\rm {\bf x}}_\mu)\subset{\rm {\bf K}}} of stationary points of f_m, m? 0{\phi_\mu, \mu \to 0} , is a Karush–Kuhn–Tucker point of problem P and a global minimizer of f on K.     

Exceptional directions for a convex body

Let K be a convex body in Rⁿ andO be a point inside K. We examine the Grassmann manifold of k-planes passing throughO. We take as exceptional the planes intersecting K along a body having at least one (k – 1)-dimensional face such that it does not have points inside the hyperfaces of body K. We prove that in the Grassmann manifold G _k ⁿ the set of such exceptional planes is of measure zero.Translated from Matematicheskie Zametki, Vol. 20, No. 3, pp. 365–371, September, 1976.The author thanks V. A. Zalgaller for aid and advice on the work.     

Volume approximation of smooth convex bodies by three-polytopes of restricted number of edges

For a given convex body K in \Bbb R³{\Bbb R}^3 with C ² boundary, let P ^c _n be the circumscribed polytope of minimal volume with at most n edges, and let P ⁱ _n be the inscribed polytope of maximal volume with at most n edges. Besides presenting an asymptotic formula for the volume difference as n tends to infinity in both cases, we prove that the typical faces of P ^c _n and P ⁱ _n are asymptotically regular triangles and squares, respectively, in a suitable sense.     

Singular sets of convex bodies and surfaces with generalized curvatures

In this paper we consider generalized surfaces with curvature measures and we study the properties of those k-dimensional subsets Σ ^k of such surfaces where the curvatures have positive density with respect to k-dimensional Hausdorff measure. Special attention is given to boundaries of convex bodies inR ³. We introduce a class of convex sets whose curvatures live only on integer dimension sets. For such convex sets we consider integral functionals depending on the curvature and the area ofK and on the curvature andH ^k of Σ ^k .     

Differentiability of a convex semigroup on Rn

It is proved that each continuous semigroup {P(t)}_t≥0 of convex operators P(t):Rⁿ→Rⁿ is continuously differentiable with respect to t. This note represents a first step towards a better understanding of semigroups formed by convex operators. We establish the differentiability of a convex semigroup in the finite dimensional case, generalizing a basic result from linear semigroup theory. Our motivation for the study of semigroups of convex operators comes from the theory of Markov decision processes. In [1] and in [2] it was shown that the maximum reward of these processes can be described by a certain nonlinear semigroup. The nonlinear operators are defined as suprema of linear operators (plus a constant), hence they are convex operators. It seems that the convexity assumption keeps its smoothing influence even in the infinite dimensional situation. We hope to discuss this in a future paper.     

Affine cross-polytopes inscribed in a convex body

Let X be an affine cross-polytope, i.e., the convex hull of n segments A ₁ B ₁,…, A _n B _n in \mathbbRⁿ {\mathbb{R}^n} that have a common midpoint O and do not lie in a hyperplane. The affine flag F(X) of X is the chain O ∈ L ₁ ⊂⋯ ⊂ L _n = \mathbbRⁿ {\mathbb{R}^n} , where L _k is the k-dimensional affine hull of the segments A ₁ B ₁,…, A _k B _k , k ≤ n. It is proved that each convex body K ⊂ \mathbbRⁿ {\mathbb{R}^n} is circumscribed about an affine cross-polytope X such that the flag F(X) satisfies the following condition for each k ∈{2,…, n}:the (k−1)-planes of support at A _k and B _k to the body L _k ∩ K in the k-plane L _k are parallel to L _k −1.Each such X has volume at least V(K)/2 ^n(n−1)/2. Bibliography: 5 titles.     

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 classes of convex sets that permit plane coverings

A family {K _i | of convex domains in the Euclidean planeR ² is said to permit a plane covering if there exist rigid motions {τ_i} such that U _i ^∞ =₁τ_i K _i =R ². Necessary and sufficient conditions that a given family of convex domains permits a plane covering are established.     

Measure of central symmetry for fields of convex figures and three-dimensional convex bodies

Let g₂³:E₂( \mathbbR³ ) ? G₂( \mathbbR³ ) \gamma_2^3:{E_2}\left( {{\mathbb{R}^3}} \right) \to {G_2}\left( {{\mathbb{R}^3}} \right) be the tautological vector bundle over the Grassmann manifold of 2-planes in \mathbbR³ {\mathbb{R}^3} , where the fiber over a plane is the plane itself regarded as a two-dimensional subspace of \mathbbR³ {\mathbb{R}^3} . A field of convex figures is given in γ₂³ if a convex figure is distinguished in each fiber so that the figure continuously depends on the fiber. It is proved that each field of convex figures in γ₂³ contains a figure K containing a centrally symmetric convex figure of area ( 4 + 16?2 ) \left( {4 + 16\sqrt {2} } \right) S(K)/31 > 0.858 S(K) (S(K) denotes the area of K), and a figure K′ that is contained in a centrally symmetric convex figure of area ( 12?2 - 8 ) \left( {12\sqrt {2} - 8} \right) S(K′)/7 < 1.282 S(K′). It is also proved that each three-dimensional convex body K is contained in a centrally symmetric convex cylinder of volume ( 36?2 - 24 ) \left( {36\sqrt {2} - 24} \right) V(K)/7 < 3.845 V(K). (Here, V(K) denotes the volume of K.) Bibliography: 5 titles.     

The Brunn-Minkowski inequality for <Emphasis Type="Italic">p</Emphasis>-capacity of convex bodies

In this paper we prove the Brunn-Minkowski inequality for the p-capacity of convex bodies (i.e convex compact sets with non-empty interior) in R ⁿ , for every p(1,n). Moreover we prove that the equality holds in such inequality if and only if the involved bodies coincide up to a translation and a dilatation. Mathematics Subject Classification (2000):35J60, 31B15, 39B62, 52A40     

A pre-hilbert space consisting of classes of convex sets

An equivalence relation is defined in the set of all bounded closed convex sets in Euclidean spaceE ⁿ. The equivalence classes are shown to be elements of a pre-Hilbert spaceA ⁿ, and geometrical relationships betweenA ⁿ andE ⁿ are investigated.     

Inequalities for convex bodies and polar reciprocal lattices inR n

LetL be a lattice and letU be ano-symmetric convex body inR ⁿ . The Minkowski functional ∥ ∥ _U ofU, the polar bodyU ⁰, the dual latticeL ^*, the covering radius μ(L, U), and the successive minima λ _i (L,U)i=1,...,n, are defined in the usual way. Let ℒ _n be the family of all lattices inR ⁿ . Given a pairU,V of convex bodies, we define and kh(U, V) is defined as the smallest positive numbers for which, given arbitraryL∈ℒ _n andu∈R ⁿ /(L+U), somev∈L ^* with ∥v∥ _V ≤sd(uv, ℤ) can be found. Upper bounds for jh(U, U ⁰), j=k, l, m, belong to the so-called transference theorems in the geometry of numbers. The technique of Gaussian-like measures on lattices, developed in an earlier paper [4] for euclidean balls, is applied to obtain upper bounds for jh(U, V) in the case whenU, V aren-dimensional ellipsoids, rectangular parallelepipeds, or unit balls inl _p ⁿ , 1≤p≤∞. The gaps between the upper bounds obtained and the known lower bounds are, roughly speaking, of order at most logn asn→∞. It is also proved that ifU is symmetric through each of the coordinate hyperplanes, then jh(U, U ⁰) are less thanCn logn for some numerical constantC.