Projection problems for symmetric polytopes

Let K⊂Rn be a convex body (a compact, convex subset with non-empty interior), ΠK its projection body. Finding the least upper bound, as K ranges over the class of origin-symmetric convex bodies, of the affine-invariant ratio V(ΠK)/V(K)ⁿ⁻¹, being called Schneider's projection problem, is a well-known open problem in the convex geometry. To study this problem, Lutwak, Yang and Zhang recently introduced a new affine invariant functional for convex polytopes in Rn. For origin-symmetric convex polytopes, they posed a conjecture for the new functional U(P). In this paper, we give an affirmative answer to the conjecture in Rn, thereby, obtain a modified version of Schneider's projection problem.     

Comparison of volumes by means of the areas of central sections

The Busemann–Petty problem asks whether origin-symmetric convex bodies in Rⁿ with smaller areas of all central hyperplane sections necessarily have smaller n-dimensional volume. The solution was completed in the end of the 1990s, and the answer is affirmative if n4 and negative if n5. Since the answer is negative in most dimensions, it is natural to ask what information about the volumes of central sections of two bodies does allow to compare the n-dimensional volumes of these bodies in all dimensions. In this article we give an answer to this question in terms of certain powers of the Laplace operator applied to the section function of the body.     

一个与投影体相关的锥体积不等式

本文研究了一个与投影体相关的锥体积不等式.利用凸函数的梯度性质,获得了n维欧氏空间中关于任意原点对称凸体的一个锥体积不等式,推进了Schneider投影问题的解决.     

Numerical decomposition of a convex function

Given then×p orthogonal matrixA and the convex functionf:R ⁿR, we find two orthogonal matricesP andQ such thatf is almost constant on the convex hull of ± the columns ofP, f is sufficiently nonconstant on the column space ofQ, and the column spaces ofP andQ provide an orthogonal direct sum decomposition of the column space ofA. This provides a numerically stable algorithm for calculating the cone of directions of constancy, at a pointx, of a convex function. Applications to convex programming are discussed.This work was supported by the National Science and Engineering Research Council of Canada (Grant No. A3388 and Summer Grant).     

On a question of A. Koldobsky

We construct an example of a non-convex star-shaped origin-symmetric body D⊂R³ such that its section function AD,ξ(t):=area(D∩{ξ^⊥+tξ}) is decreasing in t?0 for every fixed direction ξ∈S².     

Isomorphic properties of intersection bodies

We study isomorphic properties of two generalizations of intersection bodies - the class of k-intersection bodies in Rn and the class of generalized k-intersection bodies in Rn. In particular, we show that all convex bodies can be in a certain sense approximated by intersection bodies, namely, if K is any symmetric convex body in Rn and 1≤k≤n−1 then the outer volume ratio distance from K to the class can be estimated by

     

Extremum problems for the cone volume functional of convex polytopes

Lutwak, Yang and Zhang defined the cone volume functional U over convex polytopes in Rn containing the origin in their interiors, and conjectured that the greatest lower bound on the ratio of this centro-affine invariant U to volume V is attained by parallelotopes. In this paper, we give affirmative answers to the conjecture in R² and R³. Some new sharp inequalities characterizing parallelotopes in Rn are established. Moreover, a simplified proof for the conjecture restricted to the class of origin-symmetric convex polytopes in Rn is provided.     

The Busemann-Petty problem in hyperbolic and spherical spaces

The Busemann-Petty problem asks whether origin-symmetric convex bodies in Rⁿ with smaller central hyperplane sections necessarily have smaller n-dimensional volume. It is known that the answer to this problem is affirmative if n?4 and negative if n?5. We study this problem in hyperbolic and spherical spaces.     

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     

Pointwise estimates for marginals of convex bodies

We prove a pointwise version of the multi-dimensional central limit theorem for convex bodies. Namely, let μ be an isotropic, log-concave probability measure on Rn. For a typical subspace E⊂Rn of dimension nc, consider the probability density of the projection of μ onto E. We show that the ratio between this probability density and the standard Gaussian density in E is very close to 1 in large parts of E. Here c>0 is a universal constant. This complements a recent result by the second named author, where the total variation metric between the densities was considered.     

Two equivalent measures on weighted hypergraphs

Let H=(N,E,w) be a hypergraph with a node set N={0,1,…,n-1}, a hyperedge set E⊆2^N, and real edge-weights w(e) for e∈E. Given a convex n-gon P in the plane with vertices x₀,x₁,…,x_n-1 which are arranged in this order clockwisely, let each node i∈N correspond to the vertex x_i and define the area A_P(H) of H on P by the sum of the weighted areas of convex hulls for all hyperedges in H. For 0?i<j<k?n-1, a convex three-cut C(i,j,k) of N is {{i,…,j-1}, {j,…,k-1}, {k,…,n-1,0,…,i-1}} and its size c_H(i,j,k) in H is defined as the sum of weights of edges e∈E such that e contains at least one node from each of {i,…,j-1}, {j,…,k-1} and {k,…,n-1,0,…,i-1}. We show that the following two conditions are equivalent:

•

A_P(H)?A_P(H^′) for all convex n-gons P.

•

c_H(i,j,k)?c_H^′(i,j,k) for all convex three-cuts C(i,j,k).

From this property, a polynomial time algorithm for determining whether or not given weighted hypergraphs H and H^′ satisfy “A_P(H)?A_P(H^′) for all convex n-gons P” is immediately obtained.     

On removable sets for convex functions

In the present article we provide a sufficient condition for a closed set F∈R^d$F\in {\mathbb{R}}^d$ to have the following property which we call c  -removability: Whenever a continuous function f:R^d→R$f:{\mathbb{R}}^d\to \mathbb{R}$ is locally convex on the complement of F  , it is convex on the whole R^d${\mathbb{R}}^d$. We also prove that no generalized rectangle of positive Lebesgue measure in R²${\mathbb{R}}^2$ is c-removable. Our results also answer the following question asked in an article by Jacek Tabor and Józef Tabor (2010) [5]: Assume the closed set F⊂R^d$F\subset {\mathbb{R}}^d$ is such that any locally convex function defined on R^d?F${\mathbb{R}}^d?F$ has a unique convex extension on R^d${\mathbb{R}}^d$. Is F   necessarily intervally thin (a notion of smallness of sets defined by their “essential transparency” in every direction)? We prove the answer is negative by finding a counterexample in R²${\mathbb{R}}^2$.     

A theorem about antiprisms

Let P be a polytope in Rⁿ containing the origin in its interior, and let P¹ be the algebraic dual polytope of P. Let Q ? Rⁿ×[0,1] be the (n+1)-dimensional polytope that is the convex hull of P×{1} and P¹×{0}. For each face F of P, let Q(F) denote the convex hull of F×{1} and F¹×{0}, where F¹ is the dual face of P¹. Then Q is an antiprism if the set of facets of Q is precisely the collection {Q (F)} for all faces F of P. If Q is an antiprism, the correspondence between primal and dual faces of P and P¹ is manifested in the facets of Q. In this paper, necessary and sufficient conditions for the existence of antiprisms are stated and proved.     

The Newton Bracketing method for the minimization of convex functions subject to affine constraints

The Newton Bracketing method [Y. Levin, A. Ben-Israel, The Newton Bracketing method for convex minimization, Comput. Optimiz. Appl. 21 (2002) 213-229] for the minimization of convex functions f:Rⁿ→R is extended to affinely constrained convex minimization problems. The results are illustrated for affinely constrained Fermat-Weber location problems.     

Diophantine equations and the generalized Riemann hypothesis

We show that, for a listable set P of polynomials with integer coefficients, the statement “for all roots θ of all polynomials in P, the generalized Riemann hypothesis for Q(θ) holds” is Diophantine. That is, the statement is equivalent to the unsolvability of a particular Diophantine equation. This is achieved by finding a decidable property P such that the aforementioned statement may be written in the form “P holds for all natural numbers”.     

On the Stability of the p-Affine Isoperimetric Inequality

Employing the affine normal flow, we prove a stability version of the p-affine isoperimetric inequality for p≥1 in ?² in the class of origin-symmetric convex bodies. That is, if K is an origin-symmetric convex body in ?² such that it has area π and its p-affine perimeter is close enough to the one of an ellipse with the same area, then, after applying a special linear transformation, K is close to an ellipse in the Hausdorff distance.     

Contributions to max-min convex geometry. I: Segments

We give some contributions to the theory of “max-min convex geometry”, that is, convex geometry in the semimodule over the max-min semiring R_max,min=R∪{-∞,+∞}. We introduce “elementary segments” that generalize from n=2 the horizontal, vertical or oblique segments contained in the main bisector of . We show that every segment in is a concatenation of a finite number of elementary subsegments (at most 2n-1, respectively at most 2n-2, in the case of comparable, respectively, incomparable, endpoints x,y). In this first part we study “max-min segments”, and in the subsequent second part (submitted) we study “max-min semispaces” and some of their relations to “max-min convex sets”.     

On Gaussian Marginals of Uniformly Convex Bodies

Recently, Bo’az Klartag showed that arbitrary convex bodies have Gaussian marginals in most directions. We show that Klartag’s quantitative estimates may be improved for many uniformly convex bodies. These include uniformly convex bodies with power type 2, and power type p>2 with some additional type condition. In particular, our results apply to all unit-balls of subspaces of quotients of L _p for 1<p<∞. The same is true when L _p is replaced by S _p ^m , the l _p -Schatten class space. We also extend our results to arbitrary uniformly convex bodies with power type p, for 2≤p<4. These results are obtained by putting the bodies in (surprisingly) non-isotropic positions and by a new concentration of volume observation for uniformly convex bodies. Supported in part by BSF and ISF.     

Aperture-Angle and Hausdorff-Approximation of Convex Figures

The aperture angle α(x,Q) of a point x ∉ Q in the plane with respect to a convex polygon Q is the angle of the smallest cone with apex x that contains Q. The aperture angle approximation error of a compact convex set C in the plane with respect to an inscribed convex polygon Q⊂C is the minimum aperture angle of any x∈C∖Q with respect to Q. We show that for any compact convex set C in the plane and any k>2, there is an inscribed convex k-gon Q⊂C with aperture angle approximation error . This bound is optimal, and settles a conjecture by Fekete from the early 1990s. The same proof technique can be used to prove a conjecture by Brass: If a polygon P admits no approximation by a sub-k-gon (the convex hull of k vertices of P) with Hausdorff distance σ, but all subpolygons of P (the convex hull of some vertices of P) admit such an approximation, then P is a (k+1)-gon. This implies the following result: For any k>2 and any convex polygon P of perimeter at most 1 there is a sub-k-gon Q of P such that the Hausdorff-distance of P and Q is at most  . This research was supported by the Korea Research Foundation Grant funded by the Korean Government (MOEHRD) (KRF-2006-311-D00763). NICTA is funded through the Australian Government’s Backing Australia’s Ability initiative, in part through the Australian Research Council.     

On Khachiyan's algorithm for the computation of minimum-volume enclosing ellipsoids

Given A?{a¹,…,a^m}⊂R^d whose affine hull is R^d, we study the problems of computing an approximate rounding of the convex hull of A and an approximation to the minimum-volume enclosing ellipsoid of A. In the case of centrally symmetric sets, we first establish that Khachiyan's barycentric coordinate descent (BCD) method is exactly the polar of the deepest cut ellipsoid method using two-sided symmetric cuts. This observation gives further insight into the efficient implementation of the BCD method. We then propose a variant algorithm which computes an approximate rounding of the convex hull of A, and which can also be used to compute an approximation to the minimum-volume enclosing ellipsoid of A. Our algorithm is a modification of the algorithm of Kumar and Y?ld?r?m, which combines Khachiyan's BCD method with a simple initialization scheme to achieve a slightly improved polynomial complexity result, and which returns a small “core set.” We establish that our algorithm computes an approximate solution to the dual optimization formulation of the minimum-volume enclosing ellipsoid problem that satisfies a more complete set of approximate optimality conditions than either of the two previous algorithms. Furthermore, this added benefit is achieved without any increase in the improved asymptotic complexity bound of the algorithm of Kumar and Y?ld?r?m or any increase in the bound on the size of the computed core set. In addition, the “dropping idea” used in our algorithm has the potential of computing smaller core sets in practice. We also discuss several possible variants of this dropping technique.