On weakly convex star-shaped polyhedra

Weakly convex polyhedra which are star-shaped with respect to one of their vertices are infinitesimally rigid. This is a partial answer to the question as to whether every decomposable weakly convex polyhedron is infinitesimally rigid. The proof is based on a recent result of Izmestiev on the geometry of convex caps.     

A four-vertex theorem for polygons and its generalization to polytopes

A vertex v of a convex polygon P is called minimal (respectively maximal) if the circle going through v and its neighbouring vertices encloses the interior of P (respectively has no vertex of P in its interior) The main result of this paper is a generalization to the convex polytopes of R ^d of the following theorem: Every convex polygon has at least two minimal and two maximal vertices The proof uses a duality theory which translates some spherical properties of a convex polytope of R ^d into combinatorial properties of a convex polyhedron of R ^d+1.     

The Polytope of Non-Crossing Graphs on a Planar Point Set

For any set A of n points in ², we define a (3n - 3)-dimensional simple polyhedron whose face poset is isomorphic to the poset of non-crossing marked graphs with vertex set A, where a marked graph is defined as a geometric graph together with a subset of its vertices. The poset of non-crossing graphs on A appears as the complement of the star of a face in that polyhedron. The polyhedron has a unique maximal bounded face, of dimension 2n_i + n - 3 where n_i is the number of points of A in the interior of conv (A). The vertices of this polytope are all the pseudo-triangulations of A, and the edges are flips of two types: the traditional diagonal flips (in pseudo-triangulations) and the removal or insertion of a single edge. As a by-product of our construction we prove that all pseudo-triangulations are infinitesimally rigid graphs.     

Existence and sum decomposition of vertex polyhedral convex envelopes

Convex envelopes are a very useful tool in global optimization. However finding the exact convex envelope of a function is a difficult task in general. This task becomes considerably simpler in the case where the domain is a polyhedron and the convex envelope is vertex polyhedral, i.e., has a polyhedral epigraph whose vertices correspond to the vertices of the domain. A further simplification is possible when the convex envelope is sum decomposable, i.e., the convex envelope of a sum of functions coincides with the sum of the convex envelopes of the summands. In this paper we provide characterizations and sufficient conditions for the existence of a vertex polyhedral convex envelope. Our results extend and unify several results previously obtained for special cases of this problem. We then characterize sum decomposability of vertex polyhedral convex envelopes, and we show, among else, that the vertex polyhedral convex envelope of a sum of functions coincides with the sum of the vertex polyhedral convex envelopes of the summands if and only if the latter sum is vertex polyhedral.     

On the Hardness of Computing Intersection,Union and Minkowski Sum of Polytopes

For polytopes P ₁,P ₂⊂ℝ ^d , we consider the intersection P ₁∩P ₂, the convex hull of the union CH(P ₁∪P ₂), and the Minkowski sum P ₁+P ₂. For the Minkowski sum, we prove that enumerating the facets of P ₁+P ₂ is NP-hard if P ₁ and P ₂ are specified by facets, or if P ₁ is specified by vertices and P ₂ is a polyhedral cone specified by facets. For the intersection, we prove that computing the facets or the vertices of the intersection of two polytopes is NP-hard if one of them is given by vertices and the other by facets. Also, computing the vertices of the intersection of two polytopes given by vertices is shown to be NP-hard. Analogous results for computing the convex hull of the union of two polytopes follow from polar duality. All of the hardness results are established by showing that the appropriate decision version, for each of these problems, is NP-complete.     

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.     

Rigidity of certain polyhedra in $ {\bold R}^3 $

We extend the Cauchy theorem stating rigidity of convex polyhedra in . We do not require that the polyhedron be convex nor embedded, only that the realization of the polyhedron in be linear and isometric on each face. We also extend the topology of the surfaces to include the projective plane in addition to the sphere. Our approach is to choose a convenient normal to each face in such a way that as we go around the star of a vertex the chosen normals are the vertices of a convex polygon on the unit sphere. When we can make such a choice at each vertex we obtain rigidity. For example, we can prove that the heptahedron is rigid. Received: March 3, 1999; revised: December 7, 1999.     

Total Curvature and Spiralling Shortest Paths

This paper gives a partial confirmation of a conjecture of Agarwal, Har-Peled, Sharir, and Varadarajan that the total curvature of a shortest path on the boundary of a convex polyhedron in R ³ cannot be arbitrarily large. It is shown here that the conjecture holds for a class of polytopes for which the ratio of the radii of the circumscribed and inscribed ball is bounded. On the other hand, an example is constructed to show that the total curvature of a shortest path on the boundary of a convex polyhedron in R ³ can exceed 2. Another example shows that the spiralling number of a shortest path on the boundary of a convex polyhedron can be arbitrarily large.     

A combinatorial condition for the existence of polyhedral 2-manifolds

LetP denote a polyhedral 2-manifold, i.e. a 2-dimensional cell-complex inR ^d (d≧3) having convex facets, such that set (P) is homeomorphic to a closed 2-dimensional manifold. LetE be any subset of odd valent vertices ofP, andc _E its cardinality. Then for the numberc _P(E) of facets containing a vertex ofE the inequality 2c _P(E)≧c_E+1 is proved. This local combinatorial condition shows that several combinatorially possible types of polyhedral 2-manifolds cannot exist.     

Neighborly Cubical Polytopes

Neighborly cubical polytopes exist: for any n≥ d≥ 2r+2 , there is a cubical convex d -polytope C _d ⁿ whose r -skeleton is combinatorially equivalent to that of the n -dimensional cube. This solves a problem of Babson, Billera, and Chan. Kalai conjectured that the boundary of a neighborly cubical polytope C _d ⁿ maximizes the f -vector among all cubical (d-1) -spheres with 2 ⁿ vertices. While we show that this is true for polytopal spheres if n≤ d+1 , we also give a counterexample for d=4 and n=6 . Further, the existence of neighborly cubical polytopes shows that the graph of the n -dimensional cube, where n\ge5 , is ``dimensionally ambiguous' in the sense of Grünbaum. We also show that the graph of the 5 -cube is ``strongly 4 -ambiguous.' In the special case d=4 , neighborly cubical polytopes have f ₃ =(f ₀ /4) log ₂ (f ₀ /4) vertices, so the facet—vertex ratio f ₃ /f ₀ is not bounded; this solves a problem of Kalai, Perles, and Stanley studied by Jockusch. Received December 30, 1998. Online publication May 15, 2000.     

Polytopes of partitions of numbers

We study the vertices and facets of the polytopes of partitions of numbers. The partition polytope P_n is the convex hull of the set of incidence vectors of all partitions n=x₁+2x₂++nx_n. We show that the sequence P₁,P₂,…,P_n,… can be treated as an embedded chain. The dynamics of behavior of the vertices of P_n, as n increases, is established. Some sufficient and some necessary conditions for a point of P_n to be its vertex are proved. Representation of the partition polytope as a polytope on a partial algebra—which is a generalization of the group polyhedron in the group theoretic approach to the integer linear programming—allows us to prove subadditive characterization of the nontrivial facets of P_n. These facets correspond to extreme rays of the cone of subadditive functions with additional requirements p₀=p_n and p_i+p_n−i=p_n,1≤i<n. The trivial facets are explicitly indicated. We also show how all vertices and facets of the polytopes of constrained partitions—in which some numbers are forbidden to participate—can be obtained from those of the polytope P_n. All vertices and facets of P_n for n≤8 and n≤6, respectively, are presented.     

Pentagons inscribed in a closed convex curve

Two theorems are proved. Let the points A₁, A₂, A₃, A₄, and A₅ be the vertices of a convex pentagon inscribed in an ellipse, let Κ⊂ℝ² be a convex figure, and let A₀ be a fixed distinguished point of its boundary ϖK. If the sum of any two of the neighboring angles of the pentagon A₁A₂A₃A₄A₅ is greater than π or the boundary ϖK is C⁴-smooth and has positive curvature, then some affine image of the pentagon A₁A₂A₃A₄A₅ is inscribed in K and has A₀ as the image of the vertex A₁. (This is not true for arbitrary pentagons incribed in an ellipse and for arbitrary convex figures.) Bibliography: 4 titles. Translated from Zapiski Nauchnykh Seminarov POMI, Vol. 246, 1997, pp. 184–190. Translated by N. Yu. Netsvetaev.     

Interpolation by Convex Algebraic Hypersurfaces

LetΣbe the set of vertices of a convex non-degenerate polyhedron inRⁿ,n2. We suggest an algorithm to construct smooth convex algebraic hypersurfaces of degree as small as possible, going throughΣ.     

Primal—Dual Methods for Vertex and Facet Enumeration

Every convex polytope can be represented as the intersection of a finite set of halfspaces and as the convex hull of its vertices. Transforming from the halfspace (resp. vertex) to the vertex (resp. halfspace) representation is called vertex enumeration (resp. facet enumeration ). An open question is whether there is an algorithm for these two problems (equivalent by geometric duality) that is polynomial in the input size and the output size. In this paper we extend the known polynomially solvable classes of polytopes by looking at the dual problems. The dual problem of a vertex (resp. facet) enumeration problem is the facet (resp. vertex) enumeration problem for the same polytope where the input and output are simply interchanged. For a particular class of polytopes and a fixed algorithm, one transformation may be much easier than its dual. In this paper we propose a new class of algorithms that take advantage of this phenomenon. Loosely speaking, primal—dual algorithms use a solution to the easy direction as an oracle to help solve the seemingly hard direction. Received July 31, 1997, and in revised form March 8, 1998.     

Weakly redundant constraints and their impact on postoptimal analyses in LP

Suppose that in a mathematical programming problem with a smooth objective function the constraints set is formed by linear inequalities. Then, as is well known, it is possible to determine redundant constraints before the optimization procedure starts. If some of the vertices of the convex polyhedron defined by the linear constraints are degenerate, the known redundancy-determining procedures may fail. Based on the recently developed theory of degeneracy graphs (DG's for short) a procedure is suggested how to proceed in degenerate cases. Weakly redundant constraints which cause degeneracy do have some impact on sensitivity analyses with respect oo the RHS or objective function coefficients. Using again the theory of DG's this impact is analysed. Also procedures are suggested how to perform sensitivity analyses when the degeneracy of the optimal vertex is not caused only by weakly redundant constraints. Small numerical examples are used for illustration.     

Approximation of smooth convex bodies by circumscribed polytopes with respect to the surface area

Let K be a convex body with C ² boundary in the Euclidean d-space. Following the work of L. Fejes Tóth, R. Vitale, R. Schneider, P.M. Gruber, S. Glasauer and M. Ludwig, best approximation of K by polytopes of restricted number of vertices or facets is well-understood if the approximation is with respect to the volume or the mean width. In this paper we consider the circumscribed polytope P _(n) of n facets with minimal surface area, and present an asymptotic formula in terms of n for the difference of surface areas of P _(n) and K.     

Hadwiger numbers and over-dominating colourings

Motivated by Hadwiger’s conjecture, we say that a colouring of a graph is over-dominating if every vertex is joined to a vertex of each other colour and if, for each pair of colour classes C₁ and C₂, either C₁ has a vertex adjacent to all vertices in C₂ or C₂ has a vertex adjacent to all vertices in C₁.We show that a graph that has an over-dominating colouring with k colours has a complete minor of order at least 2k/3 and that this bound is essentially best possible.     

Integer Partitions from the Polyhedral Point of View

We characterize integer partitions that are convex combinations of two partitions, which connects vertices of the partition polytopes with Sidon sets and sum-free sets. We prove that all vertices of the partition polytope can be generated from a subset of support vertices with the use of two operations of merging parts. Application of either operation results in an adjacent vertex. We present also some numerical data on vertices.     

Equipartite polytopes

A polytope P with 2n vertices is called equipartite if for any partition of its vertex set into two equal-size sets V ₁ and V ₂, there is an isometry of the polytope P that maps V ₁ onto V ₂. We prove that an equipartite polytope in ℝ ^d can have at most 2d+2 vertices. We show that this bound is sharp and identify all known equipartite polytopes in ℝ ^d . We conjecture that the list is complete.     

Gaps in the numbers of vertices of cubical polytopes,I

A cubical polytope is a convex polytope of which very facet is a combinatorial cube. We ask for the numbers which occur as vertex numbers ofd-dimensional cubical polytopes, and we show, as a first step, that every cubicald-polytope for evend≥4 has an even number of vertices.