Reprint of: Refold rigidity of convex polyhedra

We show that every convex polyhedron may be unfolded to one planar piece, and then refolded to a different convex polyhedron. If the unfolding is restricted to cut only edges of the polyhedron, we identify several polyhedra that are “edge-refold rigid” in the sense that each of their unfoldings may only fold back to the original. For example, each of the 43,380 edge unfoldings of a dodecahedron may only fold back to the dodecahedron, and we establish that 11 of the 13 Archimedean solids are also edge-refold rigid. We begin the exploration of which classes of polyhedra are and are not edge-refold rigid, demonstrating infinite rigid classes through perturbations, and identifying one infinite nonrigid class: tetrahedra.     

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.     

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.     

Isohedra with nonconvex faces

An isohedron is a 3-dimensional polyhedron all faces of which are equivalent under symmetries of the polyhedron. Many well known polyhedra are isohedra; among them are the Platonic solids, the polars of Archimedean polyhedra, and a variety of polyhedra important in crystallography. Less well known are isohedra with nonconvex faces. We establish that such polyhedra must be starshaped and hence of genus 0, that their faces must be star-shaped pentagons with one concave vertex, and that they are combinatorially equivalent to either the pentagonal dodecahedron, or to the polar of the snub cube or snub dodecahedron.Supported in part by grants from the USA National Science Foundation.     

On the problem of the finiteness of the number of the combinatorial types of infinite convex polyhedra with equiangular faces

An infinite (complete) convex polyhedron with equiangular faces, that is, such that all the angles of each of its faces are equal to one another, is called irreducible if the number of monogonal faces belonging to it cannot be decreased (by identifying their sides) while preserving the equiangularity of all of the other faces and the convexity of the polyhedron itself (a lack of conditional edges). Any infinite convex polyhedron with equiangular faces can be obtained from the corresponding irreducible one by pasting in the missing number of monogons. It is proved that the number of combinatorially different irreducible polyhedra is finite, not counting three infinite series of frusta of cones with finite or infinite bases and right prisms with infinite bases. It is also established that, without exception, all infinite convex polyhedra with equiangular faces and total curvature 2are the derivatives of closed convex polyhedra with equiangular faces. The proof is carried out with the help of A. D. Milka's method from Ross. Zh. Mat., 1988, 3A830. Translated from Ukrainskii Geometricheskii Sbornik, No. 35, pp. 75–83, 1992.     

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).     

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.     

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.     

A combinatorial theory of Grünbaum's new regular polyhedra,Part II: Complete enumeration

The new regular polyhedra as defined by Branko Grünbaum in 1977 (cf. [5]) are completely enumerated. By means of a theorem of Bieberbach, concerning the existence of invariant affine subspaces for discrete affine isometry groups (cf. [3], [2] or [1]) the standard crystallographic restrictions are established for the isometry groups of the non finite (Grünbaum-)polyhedra. Then, using an appropriate classification scheme which—compared with the similar, geometrically motivated scheme, used originally by Grünbaum—is suggested rather by the group theoretical investigations in [4], it turns out that the list of examples given in [5] is essentially complete except for one additional polyhedron.So altogether—up to similarity—there are two classes of planar polyhedra, each consisting of 3 individuals and each class consisting of the Petrie duals of the other class, and there are ten classes of non planar polyhedra: two mutually Petrie dual classes of finite polyhedra, each consisting of 9 individuals, two mutually Petrie dual classes of infinite polyhedra which are contained between two parallel planes with each of those two classes consisting of three one-parameter families of polyhedra, two further mutually Petrie dual classes each of which consists of three one parameter families of polyhedra whose convex span is the whole 3-space, two further mutually Petrie dual classes consisting of three individuals each of which spanE ³ and two further classes which are closed with respect to Petrie duality, each containing 3 individuals, all spanningE ³, two of which are Petrie dual to each other, the remaining one being Petrie dual to itself.In addition, a new classification scheme for regular polygons inE ⁿ is worked out in §9.     

On universal tilers

A famous problem in discrete geometry is to find all monohedral plane tilers. It is still open to the best of our knowledge. This paper is concerned with one of its variants, that of determining all convex polyhedra whose every cross-section tiles the plane. We call such polyhedra universal tilers. We obtain that a convex polyhedron is a universal tiler only if it is a tetrahedron or a pentahedron.     

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.     

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.     

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.     

Exact join detection for convex polyhedra and other numerical abstractions

Deciding whether the union of two convex polyhedra is itself a convex polyhedron is a basic problem in polyhedral computations; having important applications in the field of constrained control and in the synthesis, analysis, verification and optimization of hardware and software systems. In such application fields though, general convex polyhedra are just one among many, so-called, numerical abstractions, which range from restricted families of (not necessarily closed) convex polyhedra to non-convex geometrical objects. We thus tackle the problem from an abstract point of view: for a wide range of numerical abstractions that can be modeled as bounded join-semilattices—that is, partial orders where any finite set of elements has a least upper bound—we show necessary and sufficient conditions for the equivalence between the lattice-theoretic join and the set-theoretic union. For the case of closed convex polyhedra—which, as far as we know, is the only one already studied in the literature—we improve upon the state-of-the-art by providing a new algorithm with a better worst-case complexity. The results and algorithms presented for the other numerical abstractions are new to this paper. All the algorithms have been implemented, experimentally validated, and made available in the Parma Polyhedra Library.     

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.     

Polyhedra dominating finitely many different homotopy types

In 1968 K. Borsuk asked: Is it true that every finite polyhedron dominates only finitely many different shapes? In this question the notions of shape and shape domination can be replaced by the notions of homotopy type and homotopy domination.We obtained earlier a negative answer to the Borsuk question and next results that the examples of such polyhedra are not rare. In particular, there exist polyhedra with nilpotent fundamental groups dominating infinitely many different homotopy types. On the other hand, we proved that every polyhedron with finite fundamental group dominates only finitely many different homotopy types. Here we obtain next positive results that the same is true for some classes of polyhedra with Abelian fundamental groups and for nilpotent polyhedra. Therefore we also get that every finitely generated, nilpotent torsion-free group has only finitely many r-images up to isomorphism.     

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.     

Constant memory routing in quasi-planar and quasi-polyhedral graphs

We address the problem of online route discovery for a class of graphs that can be embedded either in two or in three-dimensional space. In two dimensions we propose the class of quasi-planar graphs and in three dimensions the class of quasi-polyhedral graphs. In the former case such graphs are geometrically embedded in R² and have an underlying backbone that is planar with convex faces; however within each face arbitrary edges (with arbitrary crossings) are allowed. In the latter case, these graphs are geometrically embedded in R³ and consist of a backbone of convex polyhedra and arbitrary edges within each polyhedron. In both cases we provide a routing algorithm that guarantees delivery. Our algorithms need only “remember” the source and destination nodes and one (respectively, two) reference nodes used to store information about the underlying face (respectively, polyhedron) currently being traversed. The existence of the backbone is used only in proofs of correctness of the routing algorithm; the particular choice is irrelevant and does not affect the behaviour of the algorithm.     

A Rigidity Criterion for Non-Convex Polyhedra

Let P be a (non-necessarily convex) embedded polyhedron in R³, with its vertices on the boundary of an ellipsoid. Suppose that the interior of $P$ can be decomposed into convex polytopes without adding any vertex. Then P is infinitesimally rigid. More generally, let P be a polyhedron bounding a domain which is the union of polytopes C₁, . . ., C_n with disjoint interiors, whose vertices are the vertices of P. Suppose that there exists an ellipsoid which contains no vertex of P but intersects all the edges of the C_i. Then P is infinitesimally rigid. The proof is based on some geometric properties of hyperideal hyperbolic polyhedra.