Determining All Universal Tilers

A universal tiler is a convex polyhedron whose every cross-section tiles the plane. In this paper, we introduce a slight-rotating operation for cross-sections of polyhedra. By applying the operation to suitably chosen cross-sections, we prove that a convex polyhedron is a universal tiler if and only if it is a tetrahedron or a pentahedron with parallel facets.     

Calculus of convex polyhedra and polyhedral convex functions by utilizing a multiple objective linear programming solver

ABSTRACT

The article deals with operations defined on convex polyhedra or polyhedral convex functions. Given two convex polyhedra, operations like Minkowski sum, intersection and closed convex hull of the union are considered. Basic operations for one convex polyhedron are, for example, the polar, the conical hull and the image under affine transformation. The concept of a P-representation of a convex polyhedron is introduced. It is shown that many polyhedral calculus operations can be expressed explicitly in terms of P-representations. We point out that all the relevant computational effort for polyhedral calculus consists in computing projections of convex polyhedra. In order to compute projections we use a recent result saying that multiple objective linear programming (MOLP) is equivalent to the polyhedral projection problem. Based on the MOLP solver bensolve a polyhedral calculus toolbox for Matlab and GNU Octave is developed. Some numerical experiments are discussed.     

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.     

A Theorem on Strict Separability of Convex Polyhedra and Its Applications in Optimization

We propose a new approach to the strict separation of convex polyhedra. This approach is based on the construction of the set of normal vectors for the hyperplanes, such that each one strict separates the polyhedra A and B. We prove the necessary and sufficient conditions of strict separability for convex polyhedra in the Euclidean space and present its applications in optimization.     

Positivity of curvature and convexity of faces

Two-dimensional polyhedra homeomorphic to closed two-dimensional surfaces are considered in the three-dimensional Euclidean space. While studying the structure of an arbitrary face of a polyhedron, an interesting particular case is revealed when the magnitude of only one plane angle determines the sign of the curvature of the polyhedron at the vertex of this angle. Due to this observation, the following main theorem of the paper is obtained: If a two-dimensional polyhedron in the three-dimensional Euclidean space is isometric to the surface of a closed convex three-dimensional polyhedron, then all faces of the polyhedron are convex polygons.     

The Face Structure and Geometry of Marked Order Polyhedra

We study a class of polyhedra associated to marked posets. Examples of these polyhedra are Gelfand–Tsetlin polytopes and cones, as well as Berenstein–Zelevinsky polytopes—all of which have appeared in the representation theory of semi-simple Lie algebras. The faces of these polyhedra correspond to certain partitions of the underlying poset and we give a combinatorial characterization of these partitions. We specify a class of marked posets that give rise to polyhedra with facets in correspondence to the covering relations of the poset. On the convex geometrical side, we describe the recession cone of the polyhedra, discuss products and give a Minkowski sum decomposition. We briefly discuss intersections with affine subspaces that have also appeared in representation theory and recently in the theory of finite Hilbert space frames.     

A conjecture on convex polyhedra

We select a class of pyramids of a particular shape and propose a conjecture that precisely these pyramids are of greatest surface area among the closed convex polyhedra having evenly many vertices and the unit geodesic diameter. We describe the geometry of these pyramids. The confirmation of our conjecture will solve the “doubly covered disk” problem of Alexandrov. Through a connection with Reuleaux polygons we prove that on the plane the convex n-gon of unit diameter, for odd n, has greatest area when it is regular, whereas this is not so for even n.     

Unfoldings of doubly covered polyhedra and applications to space-fillers

We study unfoldings (developments) of doubly covered polyhedra, which are space-fillers in the case of cuboids and some others. All five types of parallelohedra are examples of unfoldings of doubly covered cuboids (Proposition 1). We give geometric properties of convex unfoldings of doubly covered cuboids and determine all convex unfoldings (Theorem 1). We prove that every unfolding of doubly covered cuboids has a space-filling (consisting of its congruent copies) generated by three specified translates and three specified rotations, and that all such space-fillers are derived from unfoldings of doubly covered cuboids (Theorem 2). Finally, we extend these results from cuboids to polyhedra which are fundamental regions of the Coxeter groups generated by reflections in the 3-space and which have no obtuse dihedral angles (Theorem 3).     

Polybasic polyhedra: structure of polyhedra with edge vectors of support size at most 2

It has widely been recognized that submodular set functions and base polyhedra associated with them play fundamental and important roles in combinatorial optimization problems. In the present paper, we introduce a generalized concept of base polyhedron. We consider a class of pointed convex polyhedra in R^V whose edge vectors have supports of size at most 2. We call such a convex polyhedron a polybasic polyhedron. The class of polybasic polyhedra includes ordinary base polyhedra, submodular/supermodular polyhedra, generalized polymatroids, bisubmodular polyhedra, polybasic zonotopes, boundary polyhedra of flows in generalized networks, etc. We show that for a pointed polyhedron PR^V, the following three statements are equivalent:

(1) P is a polybasic polyhedron.

(2) Each face of P with a normal vector of the full support V is obtained from a base polyhedron by a reflection and scalings along axes.

(3) The support function of P is a submodular function on each orthant of R^V.

This reveals the geometric structure of polybasic polyhedra and its relation to submodularity.     

Local overlaps in special unfoldings of convex polyhedra

We define a notion of local overlaps in polyhedron unfoldings. We use this concept to construct convex polyhedra for which certain classes of edge unfoldings contain overlaps, thereby negatively resolving some open conjectures. In particular, we construct a convex polyhedron for which every shortest path unfolding contains an overlap. We also present a convex polyhedron for which every steepest edge unfolding contains an overlap. We conclude by analyzing a broad class of unfoldings and again find a convex polyhedron for which they all contain overlaps.     

Continuous Blooming of Convex Polyhedra

We construct the first two continuous bloomings of all convex polyhedra. First, the source unfolding can be continuously bloomed. Second, any unfolding of a convex polyhedron can be refined (further cut, by a linear number of cuts) to have a continuous blooming.     

Hamiltonicity and combinatorial polyhedra

We say that a polyhedron with 0–1 valued vertices is combinatorial if the midpoint of the line joining any pair of nonadjacent vertices is the midpoint of the line joining another pair of vertices. We show that the class of combinatorial polyhedra includes such well-known classes of polyhedra as matching polyhedra, matroid basis polyhedra, node packing or stable set polyhedra and permutation polyhedra. We show the graph of a combinatorial polyhedron is always either a hypercube (i.e., isomorphic to the convex hull of a k-dimension unit cube) or else is hamilton connected (every pair of nodes is the set of terminal nodes of a hamilton path). This implies several earlier results concerning special cases of combinatorial polyhedra.     

On Finite Linear Systems Containing Strict Inequalities

This paper deals with linear systems containing finitely many weak and/or strict inequalities, whose solution sets are referred to as evenly convex polyhedral sets. The classical Motzkin theorem states that every (closed and convex) polyhedron is the Minkowski sum of a convex hull of finitely many points and a finitely generated cone. In this sense, similar representations for evenly convex polyhedra have been recently given by using the standard version for classical polyhedra. In this work, we provide a new dual tool that completely characterizes finite linear systems containing strict inequalities and it constitutes the key for obtaining a generalization of Motzkin theorem for evenly convex polyhedra.     

Graphs of polyhedra; polyhedra as graphs

Relations between graph theory and polyhedra are presented in two contexts. In the first, the symbiotic dependence between 3-connected planar graphs and convex polyhedra is described in detail. In the second, a theory of nonconvex polyhedra is based on a graph-theoretic foundation. This approach eliminates the vagueness and inconsistency that pervade much of the literature dealing with polyhedra more general than the convex ones.     

On the convex hull of the union of certain polyhedra

We consider a finite collection of polyhedra whose defining linear systems differ only in their right hand sides. Jeroslow [5] and Blair [4] specified conditions under which the convex hull of the union of these polyhedra is defined by a system whose left hand side is the common lefthand side of the individual systems, and whose right hand side is a convex combination of the individual right hand sides. We give a new sufficient condition for this property to hold, which is often easier to recognize. In particular, we show that the condition is satisfied for polyhedra whose defining systems involve the node-arc incidence matrices of directed graphs, with certain righ hand sides. We also derive as a special case the compact linear characterization of the two terminal Steiner tree polytope given in Ball, Liu and Pulleyblank [3].     

On the enumeration of convex polyhedra

We state and justify an asymptotic formula for the number of combinatorially distinct convex polyhedra with 2n faces, all triangular.     

Finding a best approximation pair of points for two polyhedra

Given two disjoint convex polyhedra, we look for a best approximation pair relative to them, i.e., a pair of points, one in each polyhedron, attaining the minimum distance between the sets. Cheney and Goldstein showed that alternating projections onto the two sets, starting from an arbitrary point, generate a sequence whose two interlaced subsequences converge to a best approximation pair. We propose a process based on projections onto the half-spaces defining the two polyhedra, which are more negotiable than projections on the polyhedra themselves. A central component in the proposed process is the Halpern–Lions–Wittmann–Bauschke algorithm for approaching the projection of a given point onto a convex set.