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.     

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.     

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.     

Infinite Faces of a Perfect Voronoi Polyhedron

Infinite faces of perfect Voronoi polyhedra are studied. The result substantially varies depending on whether the perfect Voronoi polyhedron is considered as the closed or nonclosed convex hull of the set of Voronoi points (see Theorem 1 in Sec. 5 and Theorem 2 in Sec. 7).     

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.     

Convex polyhedra of doubly stochastic matrices—IV

Basic geometrical properties of general convex polyhedra of doubly stochastic matrices are investigated. The faces of such polyhedra are characterized, and their dimensions and facets are determined. A connection between bounded faces of doubly stochastic polyhedra and faces of transportation polytopes is established, and it is shown that there exists an absolute bound for the number of extreme points of d-dimensional bounded faces of these polyhedra.     

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.     

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

A characterization of compact convex polyhedra in hyperbolic 3-space

Summary In this paper we study the extrinsic geometry of convex polyhedral surfaces in three-dimensional hyperbolic spaceH ³. We obtain a number of new uniqueness results, and also obtain a characterization of the shapes of convex polyhedra inH ³ in terms of a generalized Gauss map. This characterization greatly generalizes Andre'ev's Theorem.Oblatum 12-XI-1991 & 29-V-1992     

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.     

Separation theorems for convex polytopes and finitely-generated cones derived from theorems of the alternative

We derive from Motzkin’s Theorem that a point can be strongly separated by a hyperplane from a convex polytope and a finitely-generated convex cone. We state a similar result for Tucker’s Theorem of the alternative. A generalisation of the residual existence theorem for linear equations which has recently been proved by Rohn [8] is a corollary. We state all the results in the setting of a general vector space over a linearly ordered (possibly skew) field.     

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.     

關於平均P葉函數

<正> §1.設函數f(z)=在單位圓|z|<1中是正則的;W表示w=f(z)將|z|>1照像到w平面上的黎曼面;以w(R)表示圓|w|≤R所掩蓋W的面積(重叠的黎曼面以重叠的次數計算)。若對任意的R>0,     

Determination of the element numbers of the regular polytopes

Let ?? be a set of n-dimensional polytopes. A set ?? of n-dimensional polytopes is said to be an element set for ?? if each polytope in ?? is the union of a finite number of polytopes in ?? identified along (n ? 1)-dimensional faces. The element number of the set ?? of polyhedra, denoted by e(??), is the minimum cardinality of the element sets for ??, where the minimum is taken over all possible element sets ${\Omega \in \mathcal{E}(\Sigma)}$ . It is proved in Theorem 1 that the element number of the convex regular 4-dimensional polytopes is 4, and in Theorem 2 that the element numbers of the convex regular n-dimensional polytopes is 3 for n ?? 5. The results in this paper together with our previous papers determine completely the element numbers of the convex regular n-dimensional polytopes for all n ?? 2.     

Representation complexity of adaptive 3D distance fields

In this paper we study the representation complexity of a kind of data structure that stores the information necessary to compute the distance from a point to a geometric body. These data structures called adaptive splitting based on cubature distance fields (ASBCDF), are binary search trees generated by the adaptive splitting based on cubature (ASBC) algorithm that adaptively subdivides the space surrounding the body into tetrahedra. Their representation complexity is measured by the number of nodes in the tree (two times the number of tetrahedra in the resulting tessellation). In the case of convex polyhedra we prove that this quantity remains bounded as the number of vertices of the polyhedra increases to infinity. Experimental results show that the number of tetrahedra in the tessellations is almost independent of the combinatorial complexity of the polyhedra. This means that the average compute time of the distance to arbitrary convex polyhedra is almost constant. Therefore, ASBCDFs are especially suitable for real time applications involving rapidly changing environments modelized with complex polyhedra.     

Antipodal convex hypersurfaces

Motivated by a conjecture of Steinhaus, we consider the mapping F, associating to each point x of a convex hypersurface the set of all points at maximal intrinsic distance from x. We first provide two large classes of hypersurfaces with the mapping F single-valued and involutive. Afterwards we show that a convex body is smooth and has constant width if its double has the above properties of F, and we prove a partial converse to this result. Additional conditions are given, to characterize the (doubly covered) balls.     

Equifacetted 4-polytopes

Many polyhedra (convex 3-polytopes) are known which occur as facets (3-faces) of convex 4-polytopes. The purpose of this paper is to determine the combinatorial types of infinitely many more polyhedra with this property. This is achieved by determining the facets of polar bicyclic polytopes.     

A convex-analysis perspective on disjunctive cuts

We treat with tools from convex analysis the general problem of cutting planes, separating a point from a (closed convex) set P. Crucial for this is the computation of extreme points in the so-called reverse polar set, introduced by E. Balas in 1979. In the polyhedral case, this enables the computation of cuts that define facets of P. We exhibit three (equivalent) optimization problems to compute such extreme points; one of them corresponds to selecting a specific normalization to generate cuts. We apply the above development to the case where P is (the closed convex hull of) a union, and more particularly a union of polyhedra (case of disjunctive cuts). We conclude with some considerations on the design of efficient cut generators. The paper also contains an appendix, reviewing some fundamental concepts of convex analysis. Supported by NSF grant DMII-0352885, ONR grant N00014-03-1-0188, INRIA grant ODW and IBM.     

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.