Search

By a zonotope we mean any set in Euclidean n-dimensional space Rn which can be written as a Minkowski (vector) sum of a finite number of line segments. A zonotope is a convex centrally-symmetric polytope, and all its faces are zonotopes. Familiar examples of three-dimensional zonotopes include the cube, rhombic dodecahedron, elongated dodecahedron (Figure 1) and truncated octahedron. Photographs of models of more complicated examples appear in [1, Plate II].

An important development in the theory of (convex) polytopes was the determination by Barnette and McMullen of the minimum and maximum of v(P) (number of vertices of P) as P ranges over all simple d-polytopes with n facets. Their results are here extended to certain pairs consisting of a polytope and one of its facets. Corollaries of our main results are the determination of the minimum and maximum of v(P) as P ranges over all simple d-polyhedra with u unbounded and n - u bounded facets, and of the minimum and maximum of v(P not F)/v(F) as (P,F) ranges over all pairs consisting of a simple d-polytope P with n facets and a facet F intersecting all other facets of P. Such pairs, called Kirkman pairs of class (d,n), are related to several aspects of linear programming, including a recent algorithm of Mattheiss for finding all vertices of a polytope defined by a system of linear inequalities. (Author)

It is shown that every rational polytope is affinely equivalent to the set of all states of a finite orthomodular lattice, and that every compact convex subset of a locally convex topological vector space is affinely homeomorphic to the set of all states of an orthomodular lattice.

In this paper we derive a generation procedure for the simple (3-valent) 3-polytopes with cyclically 5-connected graphs. (A graph is called cyclically n-connected if it cannot be broken into two components, each containing a cycle, by the removal of fewer than n edges.) We define three new types of face splitting and we show, in Theorems 16 and 17, that the simple 3-polytopes with cyclically 5-connected graphs are exactly the polytopes obtained from the dodecahedron by these face splittings.

Physical systems that have resonances corresponding to representations of multidimension symmetry groups can be constructed from electric circuit elements. Examples involving symmetries of two four‐dimensional polytopes are shown. Also a group theoretical analysis of linear constraints is described.

Jack Edmonds developed a new way of looking at extremal combinatorial problems and applied his technique with a great success to the problems of the maximal-weight degreeconstrained subgraphs. Professor C. St. J.A. Nash-Williams suggested to use Edmonds' approach in the context of hamiltonian graphs. In the present paper, we determine a new set of inequalities (the “comb inequalities”) which are satisfied by the characteristic functions of hamiltonian circuits but are not explicit in the straightforward integer programming formulation. A direct application of the linear programming duality theorem then leads to a new necessary condition for the existence of hamiltonian circuits; this condition appears to be stronger than the ones previously known. Relating linear programming to hamiltonian circuits, the present paper can also be seen as a continuation of the work of Dantzig, Fulkerson and Johnson on the traveling salesman problem.

A polytopeP is called asubpolytope of a polytopeQ if vertP ⊆ vertQ. The purpose of this paper is to construct examples of 3-dimensional polytopes which are not subpolytopes of stack polytopes. Previously no such examples were known.

In this paper is proved a formula for the number of neighbourly d-polytopes with d + 3 vertices, when d is odd.

Let S 1 . . . ,Sr be r line segments, each of non-zero length, in n-dimensional euclidean space R n . If a polytope Z is defined as the vector (Minkowski) sum (1) Z = S 1 + . . . + Sr , then the segments Si will be called the components of Z. Since we do not wish to exclude the possibility that some of the components may be parallel, the polytope Z may be written in the form (1) in many different ways. For this reason it is convenient to define a zonotope to be the polytope Z together with some specified set of components {S1 , . . . , Sr }. Figures 1, 2 and 3 show some zonotopes of 1, 2 and 3 dimensions with 4, 5 and 6 components.

In this paper is proved a formula for the number of simplicial neighbourly d-polytopes with d + 3 vertices, when d is odd.

Two different approaches to a probability problem involving convex polytopes lead to a geometric proof of an integral geometric result about mixed surface areas. The proof can be modified to cover the corresponding results about mixed volumes

Using a theorem of Butler and Goodey, and using several new reductions, we show that every simple 3-polytope with 26 or fewer vertices has a Hamiltonian circuit.

A class of polytopes is defined which includes the polytopes related to the assignment problem, the edge-matching problem on complete graphs, the multi-dimensional assignment problem, and many other set partitioning problems. Modifying some results due to Balas and Padberg, we give a constructive proof that the diameter of these polytopes is less than or equal to two. This result generalizes a result obtained by Balinski and Rusakoff in connection with the assignment problem.

All sets considered in this paper will be subsets of n-dimensional Eucidean space En. In this paper, we shall consider the ‘total edge-lengths’ of polytopes which are inscribed in a given sphere and which contain its centre. We first, however, mention some related problems considered by various authors which may be of interest to the reader.

An expository, completely elementary and self-contained account is given describing several properties of the constraint polytope of the assignment problem. In particular, it is shown that the “Hirsch conjecture” holds, and that to go from any one extreme point to any other, at most 2 extreme edges need to be traversed.

Using the techniques of Gale diagrams a simple criterion is given for determining when a given spherical complex onSn−1 ⊂En is the radial projection, from the centre ofSn−1, of a convex polytope. Previously a criterion was known only for the casen=2.

Introduction . Gale diagrams, and similar techniques, have been used in several recent investigations into the combinatorial properties of convex polytopes. Here we describe other applications, namely to problems concerning sections and projections of polytopes of a given combinatorial type. For example, in §4 we shall show that every n –dimensional convex polytope with at most n + 2 vertices possesses the universal shadow boundary (usb) property : If is a subcomplex of the boundary complex ℬ ( P ) of P , and set is homeomorphic to an ( n – 2)-sphere, then there exists a polytope P', combinatorially isomorphic to P , such that the complex corresponding to is a shadow boundary of P' . We shall also show that this is the best possible result in that polytopes with n + 3 or more vertices do not, in general, have the usb property. A second application of the method, to be described in §5, is to the construction of non-realisable complexes.

The spatial orientations of a biological organism can be identified with the elements of its rotation group. By physically realizing a group-invariant integration scheme described in this article, the growth of the organism can be made orientation independent. The integration was effected by means of a path in the group, ergodic with respect to the invariant probability distribution. The simply connected covering group, furnished with its invariant metric, is isometric to the hypersurface of a hypersphere in Euclidean four-space. The path was approximated by a mesh of points uniformly distributed on the hypersurface. Regular four-dimensional polytopes were used to construct meshes of arbitrary fineness, and graph theory was used to find the desired Hamiltonian paths. A magnetic tape was programmed to direct servo-controlled gimbals realizing the path as continuous motion of the organism.

The following problem is discussed : Is it possible to represent the nucleolus of an n-person game as a solution of a linear programming problem? An affirmative answer is given for the case that the set of payoff vectors is a polytope. An example is described, showing that the above may not be possible when the set of payoff vectors is just convex and compact.

Three algebraic methods of evaluating integrals of the form, I=∫…∫P(X N ) ∑ i=1 K H a i0 + ∏ i=1 N a ij X i dx 1 ,…, dx N , where H(x) is the unit Heaviside function and P(xN) is a polynomial in the N integration variables are described. Emphasis is placed on computer implementation of the integration techniques.

In connection with his work on singularities of surfaces, Du Val asked me to enumerate certain subgroups in the symmetry groups of the “pure Archimedean” polytopes n21 (n < 5), namely those subgroups which are generated by reflections. For the sake of completeness, I have enumerated such subgroups of all the discrete groups generated by reflections (including the symmetry groups of the regular polytopes). The work involved being somewhat intricate, several slips would have been overlooked but for the information that Du Val was able to supply from the (apparently remote) theory of surfaces.

Though phrased in geometric terms, this report is concerned with the comparative efficiency of various pivot rules for the simplex method of linear programming, in which one seeks to maximize a linear objective function by moving along the edges of the feasible region. The following three rules are considered: (1) from the vertex v, survey the adjacent vertices until a vertex w is found for which the linear function of v is less than that for w, then move to w and continue the process; (2) from the vertex v, survey all of the adjacent vertices in order to find one, say w, at which the linear function has the greatest value; then move to w and continue the process; (3) from the vertex v, survey all of the adjacent vertices in order to find one, say w, for which the slope has the greatest value; then move to w and continue the process. (Author)

This paper is written to fill an apparent gap in the literature in connection with some elementary problems of distance in finite dimensional normed linear spaces. In particular the problem of determining the distance between two polytopes in a normed n n -dimensional real vector space is considered. Special consideration is given to the case in which the norm is a twice differentiable function of its arguments and for this case a convex programming algorithm is presented. In addition several other cases are considered including the well known discrete Tchebycheff approximation. The results should find application in approximation theory.

In a finite-dimensional EUCLIDean space E , a convex polytope P is a set which is the convex hull of a finite set; here such a set P will simply be called a polytope, or, if it is d-dimensional, a d-polytope. 2) An s-/ace of P is an s-dimensional set (necessarily an s-polytope) which is either P itself or is the intersection of P with a supporting hyperplane. The number of s-faces of P will be denoted by [~(P) and the s-measure of their union by ~ ( P ) . Our section headings are as follows : 1. The functions /~ for cell-complexes 2. A pulling process 3. The functions $~ for cell-complexes 4. The functions $~ for convex polytopes 5. Inequalities for the functions $~ 6. Intersection properties of simplices 7. Sections of simplices Each polytope is a compact set, and thus the class of all polytopes in E can be metrized by the HAUSDORFF distance. Our principal aim in w 1 is to show that when the polytopes are topologized in this way, each of the functions /~ is lower semicontinuous; thus for each polytope P in E it is true t ha t all polytopes sufficiently close to P have at least as m a n y s-faces as P . In connection with various extremal problems, this result can be used to restrict a t tent ion to polytopes whose vertices are in general position, bu t for t h a t purpose the pulling process described in w 2 is more advantageous. Lower semicont inui ty of the functions $~ is established in w167 3) The reasoning of w 3, like t ha t of w 1, applies not only to convex polytopes bu t also

A set of equal regular honeycombs (or polytopes) whose vertices are altogether the vertices of one regular honeycomb (or polytope) is called a vertex-regular compound. The best known examples are the Star of David (two equilateral triangles whose vertices are the vertices of a regular hexagon) and Kepler’s Stella Octangula (two regular tetrahedra whose vertices are the vertices of a cube). An enumeration (conjectured complete) of the compound tessellations of the hyperbolic plane was given in 1964 by Coxeter. In the present paper, it is shown that there are exactly two vertex-regular compound honeycombs in hyperbolic three-space: 2 {5, 3, 4} [ 5 {4, 3, 5}] and {6, 3, 3} [ 5 (6, 3, 4}].

Steinitz’ theorem states that a graph is the graph of a 3-dimensional convex polytope if and only if it is planar and 3-connected. Grunbaum has shown that Steinitz’ proof can be modified to characterize the graphs of polytopes that are centrally symmetric or have a plane of symmetry. We show how to modify Steinitz’ proof to take care of the remaining involutory case—polytopes that are symmetric about a line.

If P is a simple 3-dimesional polytope and pi is the number of i sided faces of P then ( p + t − 1 t ) n + 1 where n is the largest number of edges on any face of P. Generalizations to non-simple polytopes and polytopes of higher genus are obtained.

Using integration over Grassmann manifolds a family of numerical characteristics is associated with every convex polytope or polyhedral cone; special cases of the new characteristics are the much studied 'solid angles,' 'angle deficiencies,' and 'exterior angles'. Euler-type equations are established for the new entities, explaining the similarities previously noted in the special cases. (Author)

A non-simpliciald-polytope is shown to have strictly fewerk-faces ([(d−1)/2]≦k≦d−1) then some simpliciald-polytope with the same number of vertices; actual numerical bounds are given. This provides a strong affirmative answer to a problem of Klee.

Random set theory is closely connected with integral geometry. After a general description, based upon the Choquet theorem, the semi-Markovian property is defined and characterized in terms of integral geometry. Applications are made to Poisson polytopes characterized by conditional invariance properties.

An n -dimensional (convex) polytope is said to have few vertices if their number does not exceed n + 3. Similarly, a simplicial n -sphere with few vertices would not contain more than n + 4 of them. We want to show that all such spheres are realizable as boundary complexes of polytopes.

Let P be a special family of convex 4-polytopes, the family of stacked 4-polytopes. For every P ϵ P we investigate the existence, the structure, and the number of 2-manifolds |M| such that M is a 2-complex contained in the 2-dimensional skeleton of P, and containing all the edges of P.

In the preceding paper, Edge represented the celebrated “cubic surface group” of order 72.6! = 51840 as the group of automorphisms of a senary quadratic form over the field of residue-classes mod 2. The object of this sequel is to compare Edge's finite space with a real space, thus identifying his non-ruled quadric in PG(5, 2) with a modular counterpart of the semi-regular polytope 221 which was discovered by Gosset in 1897.

1.1. In two-dimensional spherical or elliptic geometry we have the familiar relation between the area of a triangle and its angle-sum, ∆ = k 2 (∑ α ‒ π ), (1.11) 2 π being the measure of the whole angle at a point, and k the space-constant, or, in spherical geometry, the radius of the sphere. It is well known that in three-dimensional spherical or elliptic geometry there is no corresponding relation involving the volume of a tetrahedron. For elliptic or hyperbolic space of four dimensions it was proved by Dehn that the volume of a simplex can be expressed linearly in terms of the sums of the dihedral angles (angles at a face), angles at an edge, and angles at a vertex, but for space of five dimensions the linear relations do not involve the volume. He indicates also, in a general way, the extensions of these results for spaces of any odd or even dimensions. He shows further that these results are connected with the form of the Euler polyhedral theorem, which is expressed by a linear relation connecting the numbers of boundaries of different dimensions, and which for space of odd dimensions is not homogeneous, e. g ., N 2 — N 1 + N 0 = 2 in three dimen­sions, but for space of even dimensions is homogeneous, e. g ., N 1 — N 0 = 0 in two dimensions, N 3 — N 2 + N 1 — N 0 = 0 in four. The connection, as Dehn points out, was made use of by Legendre in a proof which he gave for the Euler formula in three dimensions. 1.2. Dehn extends this connection in detail for four and five dimensions, and states the following general results in space of dimensions R n for simplexes and for polytopes bounded entirely by simplexes : (1) In R n there are ½ n + 1 or ½( n + 1) relations (according as n is even or odd) between the numbers of boundaries of a polytope bounded by simplexes.

(1968). Characterizing a Family of Complex Polytopes Without Using Complex Coordinates. Mathematics Magazine: Vol. 41, No. 5, pp. 273-276.