Infinitesimal Rigidity of Convex Polytopes

Aleksandrov [1] proved that a simple convex d -dimensional polytope, d ≥ 3 , is infinitesimally rigid if the volumes of its facets satisfy a certain assumption of stationarity. We extend this result by proving that this assumption can be replaced by a stationarity assumption on the k -dimensional volumes of the polytope's k -dimensional faces, where k ∈{1,. . .,d-1} . Received November 20, 1997.     

Linear Networks and Convex Polytopes

It is shown that the set [G,] of immersed linear networks in that are parallel to a given immersed linear network and have the same boundary as is a convex polyhedral subset of the configuration space of movable vertices of the graph G. The dimension of [G,] is calculated, and the number of its maximal faces is estimated. As an application, the spaces of all locally minimal and weighted minimal networks with fixed boundary and topology in are described. Bibliography: 21 titles.     

Optimal Smoothing for Convex Polytopes

It is proved that, given a convex polytope P in Rⁿ, togetherwith a collection of compact convex subsets in the interiorof each facet of P, there exists a smooth convex body arbitrarilyclose to P that coincides with each facet precisely along theprescribed sets, and has positive curvature elsewhere. 2000Mathematics Subject Classification 53A07, 52B11, 53C45.     

凸多胞形的保顶单纯剖分

通过引进凸多胞形对其外部一点的阴面、阳面与平射面等概念,借助两个屏蔽引理证明Rn中任何n维凸多胞形都可以剖分为内部互不相交、以原凸多胞形的顶点集的子集为顶点集的有限个n维单纯形之并,克服了相关文献中剖分的不足,为单纯形算法提供了一种比较理想的剖分工具.     

Decomposition of Polytopes and Polynomials

Motivated by a connection with the factorization of multivariate polynomials, we study integral convex polytopes and their integral decompositions in the sense of the Minkowski sum. We first show that deciding decomposability of integral polygons is NP-complete then present a pseudo-polynomial-time algorithm for decomposing polygons. For higher-dimensional polytopes, we give a heuristic algorithm which is based upon projections and uses randomization. Applications of our algorithms include absolute irreducibility testing and factorization of polynomials via their Newton polytopes. Received December 2, 1999, and in revised form November 6, 2000. Online publication May 4, 2001.     

f-Vectors of Minkowski Additions of Convex Polytopes

The objective of this paper is to present two types of results on Minkowski sums of convex polytopes. The first is about a special class of polytopes we call perfectly centered and the combinatorial properties of the Minkowski sum with their own dual. In particular, we have a characterization of the face lattice of the sum in terms of the face lattice of a given perfectly centered polytope. Exact face counting formulas are then obtained for perfectly centered simplices and hypercubes. The second type of results concerns tight upper bounds for the f-vectors of Minkowski sums of several polytopes.     

Asymmetry of Convex Polytopes and Vertex Index of Symmetric Convex Bodies

In (Gluskin, Litvak in Geom. Dedicate 90:45–48, [2002]) it was shown that a polytope with few vertices is far from being symmetric in the Banach–Mazur distance. More precisely, it was shown that Banach–Mazur distance between such a polytope and any symmetric convex body is large. In this note we introduce a new, averaging-type parameter to measure the asymmetry of polytopes. It turns out that, surprisingly, this new parameter is still very large, in fact it satisfies the same lower bound as the Banach–Mazur distance. In a sense it shows the following phenomenon: if a convex polytope with small number of vertices is as close to a symmetric body as it can be, then most of its vertices are as bad as the worst one. We apply our results to provide a lower estimate on the vertex index of a symmetric convex body, which was recently introduced in (Bezdek, Litvak in Adv. Math. 215:626–641, [2007]). Furthermore, we give the affirmative answer to a conjecture by Bezdek (Period. Math. Hung. 53:59–69, [2006]) on the quantitative illumination problem.     

Unions of Fat Convex Polytopes Have Short Skeletons

The skeleton of a polyhedral set is the union of its edges and vertices. Let \(\mathcal {P}\) be a set of fat, convex polytopes in three dimensions with n vertices in total, and let f _max be the maximum complexity of any face of a polytope in \(\mathcal {P}\). We prove that the total length of the skeleton of the union of the polytopes in \(\mathcal {P}\) is at most O(α(n)?log^? n?logf _max) times the sum of the skeleton lengths of the individual polytopes.     

Maximal f-Vectors of Minkowski Sums of Large Numbers of Polytopes

It is known that in the Minkowski sum of r polytopes in dimension d, with r<d, the number of vertices of the sum can be as high as the product of the number of vertices in each summand. However, the number of vertices for sums of more polytopes was unknown so far.     

The Randomized Integer Convex Hull

Let K R^d be a sufficiently round convex body (the ratio of the circumscribed ball to the inscribed ball is bounded by a constant) of a sufficiently large volume. We investigate the randomized integer convex hull I_L(K) = conv (K L), where L is a randomly translated and rotated copy of the integer lattice Z^d. We estimate the expected number of vertices of I_L(K), whose behaviour is similar to the expected number of vertices of the convex hull of Vol K random points in K. In the planar case we also describe the expectation of the missed area Vol (K \ I_L(K)). Surprisingly, for K a polygon, the behaviour in this case is different from the convex hull of random points.     

On the Exact Maximum Complexity of Minkowski Sums of Polytopes

We present a tight bound on the exact maximum complexity of Minkowski sums of polytopes in ?³. In particular, we prove that the maximum number of facets of the Minkowski sum of k polytopes with m ₁,m ₂,…,m _k facets, respectively, is bounded from above by \(\sum_{1\leq i. Given k positive integers m ₁,m ₂,…,m _k , we describe how to construct k polytopes with corresponding number of facets, such that the number of facets of their Minkowski sum is exactly \(\sum_{1\leq i. When k=2, for example, the expression above reduces to 4m ₁ m ₂?9m ₁?9m ₂+26.     

On the Graph Connectivity of Skeleta of Convex Polytopes

Given a d-dimensional convex polytope P and nonnegative integer k not exceeding d−1, let denote the simple graph on the node set of k-dimensional faces of P in which two such faces are adjacent if there exists a (k+1)-dimensional face of P which contains them both. The graph is isomorphic to the dual graph of the (d−k)-dimensional skeleton of the normal fan of P. For fixed values of k and d, the largest integer m such that is m-vertex-connected for all d-dimensional polytopes P is determined. This result generalizes Balinski’s theorem on the one-dimensional skeleton of a d-dimensional convex polytope. Supported by the 70/4/8755 ELKE Research Fund of the University of Athens.     

Ehrhart Polynomials of 3-Dimensional Simple Integral Convex Polytopes

The author gives an explicit formula on the Ehrhart polynomial of a 3-dimensional simple integral convex polytope by using toric geometry.     

计算幂和多项式的矩阵方法

利用矩阵给出了计算幂和多项式的统一方法.     

Integer Optimization on Convex Semialgebraic Sets

Let Y be a convex set in Re ^k defined by polynomial inequalities and equations of degree at most d ≥ 2 with integer coefficients of binary length at most l . We show that if the set of optimal solutions of the integer programming problem min is not empty, then the problem has an optimal solution of binary length ld ^O(k4) . For fixed k , our bound implies a polynomial-time algorithm for computing an optimal integral solution y ^* . In particular, we extend Lenstra's theorem on the polynomial-time solvability of linear integer programming in fixed dimension to semidefinite integer programming. Received August 3, 1998, and in revised form March 22, 1999.