Introduction
David Eppstein
Dept. of Information & Computer Science
U.C. Irvine, CA, 92717
http://www.ics.uci.edu/~eppstein/
Introduction
A zonotope is a set of points in d-dimensional space constructed from vectors vi by taking the sum of ai vi where each ai is a scalar between 0 and 1. Different choices of scalars give different points, and the zonotope is the set of all such points. Alternately it can be viewed as a Minkowski sum of line segments connecting the origin to the endpoint of each vector. It is called a zonotope because the faces parallel to each vector form a so-called zone wrapping around the polytope. A zonohedron is just a three-dimensional zonotope. Zonohedra include many familiar polyhedra including cubes, truncated octahedra, and rhombic dodecahedra. Towle [T96] recently described Mathematica code for polar zonohedra, generated by vectors evenly spaced around a circular cone. This notebook contains code for constructing zonotopes and displaying zonohedra without such restrictions on the generators.
There is some confusion in the definition of zonotopes; Wells [W91] requires the generating vectors to be in general position (all d-tuples of vectors must span the whole space), so that all the faces of the zonotope are parallelotopes. Others [BEG95,Z95] do not make this restriction. Coxeter [C73] starts with one definition but soon switches to the other. We use the unrestricted definition here.
The combinatorics of the faces of a zonotope are equivalent to those of an arrangement of hyperplanes in a space of one fewer dimension, so for instance zonohedra correspond to planar line arrangements. This can be most easily seen by considering the space of d-dimensional hyperplanes tangent to the zonotope. The space of all d-dimensional unit vectors can be seen as a unit sphere, equivalent to oriented projective (d-1)-space. For any given unit vector, there is a unique hyperplane normal to the vector and tangent to the zonotope at some kind of face. One can swing a hyperplane tangent to a k-dimensional face through a collection of angles with (d-1-k) degrees of freedom; for instance, tangent planes to a facet of a polyhedron must lie on the facet itself (no degrees of freedom), tangent planes to an edge have one degree of freedom, and tangent planes to a vertex have two degrees of freedom. Thus if we divide up the the tangent space according to which zonotope face each tangent touches, we get a decomposition of the tangent space into cells of varying dimensions. The tangent plane has fewer degrees of freedom when it swings around high dimensional faces, so high dimensional faces of the zonotope correspond to low dimensional cells in the tangent space decomposition. For the zonotope corresponding to a single vector (a line segment), this decomposition of the tangent space would be given by a single hyperplane corresponding to the tangents parallel to the segment, and partitioning the rest of the tangents into two subsets, one for each endpoint of the segment. But the decomposition corresponding to a Minkowski sum is formed by overlaying the decompositions corresponding to the two summands, so the cell decomposition of a zonotope's tangent space is formed by overlaying a collection of hyperplanes. Each zone of the zonotope corresponds to a hyperplane in this arrangement.
Because of this correspondence, we can construct zonotopes in the same amount of time as it takes to construct hyperplane arrangements in the tangent space, O(n^(d-1)). The arrangement tells us how the zonotope's faces connect to each other, and the actual vertex coordinates are not hard to find within the same time bound. In particular it would take O(n^2) time to construct a zonohedron from an initial set of n vectors. However our implementation uses a slower algorithm better suited to the functional nature of Mathematica programming. We first find the subsets of vectors corresponding to the faces of the zonotope. These subsets are determined incrementally, by combining each new vector with previously generated subsets, and then forming additional faces pairing the new vector with any remaining old vectors. Once we have generated all faces, we determine coordinates for their vertices (recursively, since each face is again a zonotope in one lower dimension) and lift them into position by adding appropriate subsets of the vectors.
Implementation
Coplanarity and Orientation Test
In the face generation stage, we represent a face by the indices of the vectors generating it. When we add a new vector to the zonohedron, we test it against each face and determine whether it is coplanar by computing the determinant of a matrix formed by the new vector and d-1 of the vectors already in the face; it is coplanar exactly when this determinant is zero, and if so it gets added to the list of indices for that face. In the face placement stage, we instead represent a face by the coordinates of its vertices, so we need code to translate between the two representations. Once we have found the coordinates of a face recursively as a lower-dimensional zonotope, we lift two copies of it in place by using a similar determinant computation to determine which vectors to add to each copy.
In order to compute lower-dimensional faces recursively, we need a way of testing signs of determinants when there are fewer than d vectors involved. We do this by including enough extra vectors to make up a d*d matrix. The extra vectors are chosen on the moment curve (x,x^2,x^3,...), so that they are independent of each other and (hopefully) of the inputs.
ZSignTest[vv_,f_] :=
Det [ Part[vv,f] ~Join~
Table[(i+200)^j,
{i,Length[vv[[1]]]-Length[f]},
{j,Length[vv[[1]]]}]]
As described earlier, we generate faces (as subsets of vectors) incrementally, adding one vector at a time to our zonotope. Adding one vector has two parts: including it in the faces with which it is coplanar, and then making new faces not coplanar to any existing faces.
ZOldFaces[vv_,ff_,i_,d_] := (ZAddToFace[vv, #, i, d])& /@ ff
This routine tests whether to add a new vector to an existing face.
ZAddToFace[vv_,f_,i_,d_] := If[ Length[f] < (d-1) || ZSignTest[vv, Append[Take[f,d-1],i]] == 0, Append[f,i], f ]
To generate the new faces, we make all (d-1)-tuples of indices that have index i as their largest element, and that are not subsets of the indices in existing faces. If d is 2, this set of tuples is either the singleton {i} or nothing at all, depending on whether i is in any face. Otherwise, we combine tuples generated recursively for all j<i, passing into the recursion only those faces that contain index i, and appending i to each recursively generated tuple.
ZTuples[i_,1,ff_] :=
If[MemberQ[Flatten[ff],i], {}, {{i}}];
ZTuples[i_,d_,ff_] :=
(Append[#,i]&) /@
ZAllTuples[i-1,d-1,Select[ff,MemberQ[#,i]&]]
ZAllTuples[i_,1,ff_] :=
List /@ Complement[Range[i], Flatten[ff]];
ZAllTuples[i_,d_,ff_] :=
Join @@ Table[ZTuples[j,d,ff],{j,i}]
ZAddTuples[ff_,i_,d_] := ff ~Join~ ZTuples[i,d-1,ff]
ZNewFaces[vv_,ff_,i_,d_] := ZAddTuples[ZOldFaces[vv,ff,i,d], i, d]
ZAllFaces[vv_,d_] :=
Fold[ZNewFaces[vv,#1,#2,d]&,
{{}}, Table[i,{i,Length[vv]}]]
ZLiftAll[vv_,ff_,d_] := Join @@ Map[ZLiftFace[vv,#,d]&,ff]
The next two routines convert faces from subsets of indices to coordinates. This is simply a recursive call to Zonotope, except that when the face is zero-dimensional the result is just a single point at the origin. To save some time, we handle specially the case when the face is one-dimensional and (as is usually the case) has only one vector; calling Zonotope recursively in this case would perform an unnecessary determinant sign test.
ZOrigin[vv_] := Table[ 0, {Length[ vv[[1]] ]} ]
ZFace[vv_,f_,1] := ZOrigin[vv];
ZFace[vv_,{i_},2] := {ZOrigin[vv],vv[[i]]};
ZFace[vv_,f_,d_] := Zonotope[ Part[vv,f], d-1 ];
The remaining routines in this section are concerned with translating the converted faces into their appropriate positions in space. Each face appears in two copies, and each vector not contributing to the face is used to shift exactly one of the copies. Which one is determined by another determinant calculation.
ZLiftVector[vv_,f_,i_,d_] :=
If [ MemberQ[f, i], {ZOrigin[vv],ZOrigin[vv]},
If [ ZSignTest[vv, Append[Take[f,d-1],i]] < 0,
{vv[[i]], ZOrigin[vv]},
{ZOrigin[vv], vv[[i]]}]]
I want to add the same vector to all level-one lists in a nested list structure, but Mathematica doesn't let Plus work this way (although it does work with scalars...)
ZVecPlus[a_,v_] := If[Head[First[a]] === List, ZVecPlus[#,v]& /@ a, a+v]
ZLiftFace[vv_,f_,d_] :=
{#1 ~ZVecPlus~ #2[[1]], #1 ~ZVecPlus~ #2[[2]]}& [
ZFace[vv,f,d],
Sum[ZLiftVector[vv,f,j,d],{j,Length[vv]}]]
Zonotope[vv_,d_] := ZLiftAll[vv,ZAllFaces[vv,d],d]
The general zonotope code will produce a recursive description in which 2d faces are lists of 1d edges, etc. For nice drawings of zonohedra we need to convert these lists of edges into a single polygon.
ZNext[f_,e_] :=
Join @@ Map[
If[ e[[2]] == #[[1]] && e[[1]] != #[[2]], #,
If[ e[[2]] == #[[2]] && e[[1]] != #[[1]],
Reverse[#], {}]]&, f]
ZMakePolygon[f_] := First /@ NestList[ ZNext[f,#]&, f[[1]], Length[f]-1 ]
Zonohedron[vv_] :=
Show[Graphics3D[Polygon /@ ZMakePolygon /@
Zonotope[N[vv],3]],
ViewPoint->{12,3,5},
Boxed -> False]
Zonohedron[{{1,0,0},{0,1,0},{0,0,1}}]
Prisms
Zonohedron[{{1,Sqrt[3],0},{1,-Sqrt[3],0},{2,0,0},{0,0,2}}]
Zonohedron[{{2,0,0},{0,2,0},{0,0,2},
{Sqrt[2],Sqrt[2],0},{Sqrt[2],-Sqrt[2],0}}]
The Truncated Octahedron
The octahedron itself is not a zonohedron, since its faces are triangular and do not form zones. However if one uses the edges of the octahedron as generators, one gets this zonohedron, in which the triangular faces of the octahedron have been truncated to hexagons and squares added to connect them. The twelve octahedron edges come in six pairs, so there are six generators. This shape can fill space without leaving any gaps.
Zonohedron[{{1,1,0},{1,-1,0},{1,0,1},{1,0,-1},
{0,1,1},{0,1,-1}}]
The Rhombic Dodecahedron
This is the dual to the cuboctahedron, an Archimedean solid formed by combining the six squares of a cube with the eight triangles of an octahedron. The cuboctahedron itself is not a zonohedron because of its triangular faces.
Zonohedron[{{1,1,1},{1,-1,1},{1,1,-1},{1,-1,-1}}]
The Extended Rhombic Dodecahedron
This zonotope is noteworthy for (like the cube, hexagonal prism, truncated octahedron, and rhombic dodecahedron) being able to fill space without leaving any gaps. The one here is drawn with different angles from the rhombic dodecahedron itself, to make the hexagonal sides regular.
Zonohedron[{{0,Sqrt[3],1},{Sqrt[3],0,1},
{0,-Sqrt[3],1},{-Sqrt[3],0,1},
{0,0,2}}]
The Truncated Cuboctahedron
As can be seen from its set of generators, this is the Minkowski sum of a cube and a truncated octahedron. It is also known as the Great Rhombicuboctahedron.
Zonohedron[{{1,1,0},{1,-1,0},{1,0,1},{1,0,-1},
{0,1,1},{0,1,-1},
{Sqrt[2],0,0},{0,Sqrt[2],0},{0,0,Sqrt[2]}}]
The Truncated Rhombic Dodecahedron
This is the Minkowski sum of a cube and a rhombic dodecahedron. The hexagons can not be regular, although they do have all sides the same length, since three regular hexagons would meet in a flat solid angle instead of the corners here. Although this shape does not fill space on its own, it can be combined with cubes in a regular space-filling pattern.
Zonohedron[{{1,1,1},{1,1,-1},{1,-1,1},{1,-1,-1},
{Sqrt[3],0,0},{0,Sqrt[3],0},{0,0,Sqrt[3]}}]
The Truncated Small Rhombicuboctahedron
This is the Minkowski sum of a cube, a truncated octahedron, and a rhombic dodecahedron. Some of the octagonal faces are non-regular.
Zonohedron[{{1,1,0},{1,-1,0},{1,0,1},{1,0,-1},
{0,1,1},{0,1,-1},
{Sqrt[2/3],Sqrt[2/3],Sqrt[2/3]},
{Sqrt[2/3],Sqrt[2/3],-Sqrt[2/3]},
{Sqrt[2/3],-Sqrt[2/3],Sqrt[2/3]},
{Sqrt[2/3],-Sqrt[2/3],-Sqrt[2/3]},
{Sqrt[2],0,0},{0,Sqrt[2],0},{0,0,Sqrt[2]}}]
The Rhombic Triacontahedron
This is the dual of the icosidodecahedron, one of the Archimedian solids that (like the cuboctahedron) is not a zonohedron as it has odd faces.
Zonohedron[{{1,0,-GoldenRatio},{1,0,GoldenRatio},
{0,-GoldenRatio,1},{0,GoldenRatio,1},
{-GoldenRatio,1,0},{GoldenRatio,1,0}}]
The Truncated Icosidodecahedron
This is also known as the Great Rhombicosidodecahedron. It may not be obvious, but the generators below can be grouped into five triples of orthogonal vectors, showing that this is the Minkowski sum of five cubes.
Zonohedron[{
{1,GoldenRatio,GoldenRatio-1},{1,-GoldenRatio,GoldenRatio-1},
{1,-GoldenRatio,1-GoldenRatio},{1,GoldenRatio,1-GoldenRatio},
{GoldenRatio,1-GoldenRatio,1},{GoldenRatio,1-GoldenRatio,-1},
{GoldenRatio,GoldenRatio-1,-1},{GoldenRatio,GoldenRatio-1,1},
{GoldenRatio-1,1,GoldenRatio},{GoldenRatio-1,-1,-GoldenRatio},
{GoldenRatio-1,1,-GoldenRatio},{GoldenRatio-1,-1,GoldenRatio},
{2,0,0},{0,2,0},{0,0,2}}]
The Truncated Small Rhombicosidodecahedron
This shape is the Minkowski sum of the great rhombicosidodecahedron and the rhombic triacontahedron. As drawn here, the edges have two slightly different lengths.
Zonohedron[{{1,0,-GoldenRatio},{1,0,GoldenRatio},
{0,-GoldenRatio,1},{0,GoldenRatio,1},
{-GoldenRatio,1,0},{GoldenRatio,1,0},
{1,GoldenRatio,GoldenRatio-1},{1,-GoldenRatio,GoldenRatio-1},
{1,-GoldenRatio,1-GoldenRatio},{1,GoldenRatio,1-GoldenRatio},
{GoldenRatio,1-GoldenRatio,1},{GoldenRatio,1-GoldenRatio,-1},
{GoldenRatio,GoldenRatio-1,-1},{GoldenRatio,GoldenRatio-1,1},
{GoldenRatio-1,1,GoldenRatio},{GoldenRatio-1,-1,-GoldenRatio},
{GoldenRatio-1,1,-GoldenRatio},{GoldenRatio-1,-1,GoldenRatio},
{2,0,0},{0,2,0},{0,0,2}}]
-Graphics3D-
A Ukrainian Easter Egg
Like the polar zonohedra mentioned earlier, this zonohedron has its generating vectors evenly spaced on cones. Unlike the polar zonohedra, though, there are two cones, nested inside each other, with the vectors on the inner cone being given much shorter lengths than the vectors on the outer cone. As can be seen from the drawing, the overall shape is like that generated only by the larger vectors, but with an additional zigzag belt of many long thin faces generated by the other vectors.
This example comes from my paper [BEG95] in which we studied the problem of, given a collection of points each having an unknown weight somewhere between two known bounds, finding the set of all possible weighted averages of the points. This turns out to be equivalent to finding a perspective projection of a zonotope (such as the outlines of the drawings constructed here by Mathematica). If one further knows what the sum of the weights should be, the problem instead turns into one of finding the shape formed by a slice through a zonotope. And if this sum is known but bounds on it are known, the problem becomes one of taking two parallel slices through a zonotope and performing a perspective projection on the resulting drum shape. Zonotopes resembling the shape below were used to show that the latter two problems could have complexity n^d, even though the first problem's complexity is only O(n^(d-1)) owing to the fact that it can be further transformed into one of finding a convex surface in a (d-1)-dimensional hyperplane arrangement.
My co-authors and I gave this its name because of its festive appearance, but of course real Easter eggs are neither pointy nor centrally symmetric. For some reason, with the choice of parameters below, Mathematica insists on cutting off the shape's top and bottom vertices, adding to the egg-like appearance of the image.
ZoneCircle[n_,x_,y_] :=
N[Table[{y Cos[2 Pi (i+.5) / n], y Sin[2 Pi (i+.5)/ n], x},
{i,n}]]
Zonohedron[ZoneCircle[9,1,1] ~Join~ ZoneCircle[7,.1,.005]]
Permutation Polytopes
For any k, the convex hull of the k-dimensional vectors formed by permuting the coordinates of (1,2,...,k) is called a permutation polytope or permutahedron [Z95]. Its edges correspond to permutations adjacent by a single transposition, so any two of the k! vertices are connected by a path of O(n^2) edges (think of bubble sort). Although it naturally lives in k-dimensional space, the permutation polytope is only (k-1) dimensional because all vertices satisfy the linear relation Sum[v[[i]]]=k(k-1)/2. As it turns out, these polytopes are zonotopes.
We demonstrate for k=4; although it is hard to tell from the coordinates, the result is isometric to the truncated octahedron. We shift the polytope with ZVecPlus to make the vertices land in the correct places and use ZMakePolygon to show the structure more clearly. The output consists of a list of faces, each a list of vertex coordinates. Hexagonal faces correspond to transpositions among a triple of values while squares correspond to pairs of disjoint transpositions. The reader may find it an interesting exercise to match up the coordinates here with the picture of the truncated octahedron shown earlier.
ZMakePolygon /@
Zonotope[{{1,-1,0,0},{1,0,-1,0},{1,0,0,-1},
{0,1,-1,0},{0,1,0,-1},{0,0,1,-1}},3] ~ZVecPlus~
{1,2,3,4}
{{{1, 2, 3, 4}, {2, 1, 3, 4}, {3, 1, 2, 4},
{3, 2, 1, 4}, {2, 3, 1, 4}, {1, 3, 2, 4}},
{{2, 3, 4, 1}, {3, 2, 4, 1}, {4, 2, 3, 1},
{4, 3, 2, 1}, {3, 4, 2, 1}, {2, 4, 3, 1}},
{{2, 3, 1, 4}, {3, 2, 1, 4}, {4, 2, 1, 3},
{4, 3, 1, 2}, {3, 4, 1, 2}, {2, 4, 1, 3}},
{{1, 2, 4, 3}, {2, 1, 4, 3}, {3, 1, 4, 2},
{3, 2, 4, 1}, {2, 3, 4, 1}, {1, 3, 4, 2}},
{{2, 4, 3, 1}, {3, 4, 2, 1}, {3, 4, 1, 2},
{2, 4, 1, 3}, {1, 4, 2, 3}, {1, 4, 3, 2}},
{{3, 1, 4, 2}, {4, 1, 3, 2}, {4, 1, 2, 3},
{3, 1, 2, 4}, {2, 1, 3, 4}, {2, 1, 4, 3}},
{{3, 1, 2, 4}, {4, 1, 2, 3}, {4, 2, 1, 3},
{3, 2, 1, 4}}, {{1, 3, 4, 2}, {2, 3, 4, 1},
{2, 4, 3, 1}, {1, 4, 3, 2}},
{{1, 3, 2, 4}, {2, 3, 1, 4}, {2, 4, 1, 3},
{1, 4, 2, 3}}, {{3, 1, 4, 2}, {4, 1, 3, 2},
{4, 2, 3, 1}, {3, 2, 4, 1}},
{{1, 2, 3, 4}, {1, 3, 2, 4}, {1, 4, 2, 3},
{1, 4, 3, 2}, {1, 3, 4, 2}, {1, 2, 4, 3}},
{{4, 1, 2, 3}, {4, 2, 1, 3}, {4, 3, 1, 2},
{4, 3, 2, 1}, {4, 2, 3, 1}, {4, 1, 3, 2}},
{{3, 4, 2, 1}, {4, 3, 2, 1}, {4, 3, 1, 2},
{3, 4, 1, 2}}, {{1, 2, 4, 3}, {2, 1, 4, 3},
{2, 1, 3, 4}, {1, 2, 3, 4}}}
M. Bern, D. Eppstein, L. Guibas, J. Hershberger, S. Suri, and J. Wolter. The centroid of points with approximate weights. Proc. 3rd Eur. Symp. Algorithms, Lecture Notes in Computer Science 979, Springer, 1995, pp. 460-472.
H.S.M. Coxeter. Regular Polytopes. Dover, 1973, pp. 27-30.
R. Towle. Polar Zonohedra. The Mathematica J. 6(2), 1996, pp. 8-12.
D. Wells. The Penguin Dictionary of Curious and Interesting Geometry. Penguin, 1995, pp. 274-275.
G. Ziegler. Lectures on Polytopes. Springer, 1995, pp. 198-208.