The Surface Area Deviation of the Euclidean Ball and a Polytope

While there is extensive literature on approximation of convex bodies by inscribed or circumscribed polytopes, much less is known in the case of generally positioned polytopes. Here we give upper and lower bounds for approximation of convex bodies by arbitrarily positioned polytopes with a fixed number of vertices or facets in the symmetric surface area deviation.     

Error of Asymptotic Formulae for Volume Approximation of Convex Bodies in

 We estimate the error of asymptotic formulae for volume approximation of sufficiently differentiable convex bodies by circumscribed convex polytopes as the number of facets tends to infinity. Similar estimates hold for approximation with inscribed and general polytopes and for vertices instead of facets. Our result is then applied to estimate the minimum isoperimetric quotient of convex polytopes as the number of facets tends to infinity.     

Error of Asymptotic Formulae for Volume Approximation of Convex Bodies in

 We estimate the error of asymptotic formulae for volume approximation of sufficiently differentiable convex bodies by circumscribed convex polytopes as the number of facets tends to infinity. Similar estimates hold for approximation with inscribed and general polytopes and for vertices instead of facets. Our result is then applied to estimate the minimum isoperimetric quotient of convex polytopes as the number of facets tends to infinity. Received 16 July 2001     

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.     

Correlation polytopes: Their geometry and complexity

A family of polytopes, correlation polytopes, which arise naturally in the theory of probability and propositional logic, is defined. These polytopes are tightly connected to combinatorial problems in the foundations of quantum mechanics, and to the Ising spin model. Correlation polytopes exhibit a great deal of symmetry. Exponential size symmetry groups, which leave the polytope invariant and act transitively on its vertices, are defined. Using the symmetries, a large family of facets is determined. A conjecture concerning the full facet structure of correlation polytopes is formulated (the conjecture, however, implies that NP=co-NP).Various complexity results are proved. It is shown that deciding membership in a correlation polytope is an NP-complete problem, and deciding facets is probably not even in NP. The relations between the polytope symmetries and its complexity are indicated.     

Optimal growth order of the number of vertices and facets in the class of Hausdorff methods for polyhedral approximation of convex bodies

The internal polyhedral approximation of convex compact bodies with twice continuously differentiable boundaries and positive principal curvatures is considered. The growth of the number of facets in the class of Hausdorff adaptive methods of internal polyhedral approximation that are asymptotically optimal in the growth order of the number of vertices in approximating polytopes is studied. It is shown that the growth order of the number of facets is optimal together with the order growth of the number of vertices. Explicit expressions for the constants in the corresponding bounds are obtained.     

On Gale and braxial polytopes

Cyclic polytopes are characterized as simplicial polytopes satisfying Gale’s evenness condition (a combinatorial condition on facets relative to a fixed ordering of the vertices). Periodically-cyclic polytopes are polytopes for which certain subpolytopes are cyclic. Bisztriczky discovered a class of periodically-cyclic polytopes that also satisfy Gale’s evenness condition. The faces of these polytopes are braxtopes, a certain class of nonsimplicial polytopes studied by the authors. In this paper we prove that the periodically-cyclic Gale polytopes of Bisztriczky are exactly the polytopes that satisfy Gale’s evenness condition and are braxial (all faces are braxtopes). The existence of other periodically-cyclic Gale polytopes is open. Supported in part by a grant from the University of Kansas General Research Fund and by a Natural Sciences and Engineering Research Council of Canada Discovery Grant. Received: 20 September 2006     

Least distance methods for the scheme of polytopes

Methods are described and APL-codes are supplied to find vertices, edges, other faces and facets of polytopes given by point sets. The basic subroutine is a simplicial decomposition version of least distance, i.e. quadratic, programming. Computational experience indicates high efficiency.     

(1,k)-configurations and facets for packing problems

A new class of facets for knapsack polytopes is obtained. This class of inequalities is shown to define a polytope with zero–one vertices only. A combinatorial inequality is obtained from Fulkerson's max—max inequality.     

On the facets of the secondary polytope

The secondary polytope of a point configuration A is a polytope whose face poset is isomorphic to the poset of all regular subdivisions of A. While the vertices of the secondary polytope - corresponding to the triangulations of A - are very well studied, there is not much known about the facets of the secondary polytope.The splits of a polytope, subdivisions with exactly two maximal faces, are the simplest examples of such facets and the first that were systematically investigated. The present paper can be seen as a continuation of these studies and as a starting point of an examination of the subdivisions corresponding to the facets of the secondary polytope in general. As a special case, the notion of k-split is introduced as a possibility to classify polytopes in accordance to the complexity of the facets of their secondary polytopes. An application to matroid subdivisions of hypersimplices and tropical geometry is given.     

Decomposability of polytopes and polyhedra

In this paper decomposability of polytopes (and polyhedral sets) is studied by investigating the space of affine dependences of the vertices of the dual polytope. This turns out to be a fruitful approach and leads to several new results, as well as to simpler proofs and generalizations of known results. One of the new results is that a 3-polytope with more vertices than facets is decomposable; this leads to a characterization of the decomposability of 3-polytopes.     

Self-Duality of Polytopes and its Relations to Vertex Enumeration and Graph Isomorphism

We study the complexity of determining whether a polytope given by its vertices or facets is combinatorially isomorphic to its polar dual. We prove that this problem is Graph Isomorphism hard, and that it is Graph Isomorphism complete if and only if Vertex Enumeration is Graph Isomorphism easy. To the best of our knowledge, this is the first problem that is not equivalent to Vertex Enumeration and whose complexity status has a non-trivial impact on the complexity of Vertex Enumeration irrespective of whether checking Self-duality turns out to be strictly harder than Graph Isomorphism or equivalent to Graph Isomorphism. The constructions employed in the proof yield a class of self-dual polytopes that are interesting on their own. In particular, this class of self-dual polytopes has the property that the facet-vertex incident matrix of the polytope is transposable if and only if the matrix is symmetrizable as well. As a consequence of this construction, we also prove that checking self-duality of a polytope, given by its facet-vertex incidence matrix, is Graph Isomorphism complete, thereby answering a question of Kaibel and Schwartz.     

The lower and upper bound problems for cubical polytopes

We construct a family of cubical polytypes which shows that the upper bound on the number of facets of a cubical polytope (given a fixed number of vertices) is higher than previously suspected. We also formulate a lower bound conjecture for cubical polytopes.This paper was researched and written while the author was a graduate student at MIT. The author was partially supported by an NSF Graduate Fellowship.     

Long monotone paths on simple 4-polytopes

TheMonotone Upper Bound Problem (Klee, 1965) asks if the maximal numberM(d,n) of vertices in a monotone path along edges of ad-dimensional polytope withn facets can be as large as conceivably possible: IsM(d,n)=M _ubt (d,n), the maximal number of vertices that ad-polytope withn facets can have according to the Upper Bound Theorem?We show that in dimensiond=4, the answer is “yes”, despite the fact that it is “no” if we restrict ourselves to the dual-to-cyclic polytopes. For eachn≥5, we exhibit a realization of a polar-to-neighborly 4-dimensional polytope withn facets and a Hamilton path through its vertices that is monotone with respect to a linear objective function.This constrasts an earlier result, by which no polar-to-neighborly 6-dimensional polytope with 9 facets admits a monotone Hamilton path.     

Über die Symmetriegruppen von regulärseitigen Polytopen

Convex polytopes are called regular faced, if all their facets are regular. It is known, that all regular faced 3-polytopes have a nontrivial symmetry group, and also alld-polytopes with centrally symmetric facets. Here it is shown, that there ecist in fact regular facedd-polytopes with trivial symmetry group, but only ford=4. The corresponding class of polytopes is studied.