Zonohedra and Zonotopes

Complicated shapes can be formed by applying the Minkowski sum operation to relatively simple sets of vectors. Using Mathematica to display the results gives insights into the combinatorics of line arrangments, the projections of hypercubes, and the centroids ofweighted point sets.

by David Eppstein

Introduction

Zonotopes are shapes that can be defined in several different ways. First, they are polytopes in which all faces are centrally symmetric. Second, they are projections of higher dimensional hypercubes. Third, and most usefully to us, zonotopes can be defined as the Minkowski sums of families of line segments (the generators of the zonotope); the Minkowski sum of two subsets A and B of a vector space is the set { a+b | a in A, b in B }. These shapes are called zonotopes because their faces can be grouped into zones wrapping around the polytope, with each zone being the faces parallel to a generator. A zonohedron is just a three-dimensional zonotope. Zonohedra include many familiar polyhedra including cubes, truncated octahedra, and rhombic dodecahedra. Towle [Towle 1996] recently described Mathematica code for polar zonohedra, defined by generators evenly spaced around a circular cone. This notebook contains code for constructing zonotopes and displaying zonohedra without such restrictions on the generators. Translation of the generators does not change the shape of the Minkowski sum, so we will assume that all our generators are line segments with one endpoint at the origin, and represent them by vectors of coordinates of the other endpoints.

There is some confusion in the definition of zonotopes; Wells [Wells 1991] 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 [Bern, Eppstein, Guibas, Hersberger, Suri, and Wolter 1995, Ziegler 1995] do not make this restriction. Coxeter [Coxeter 1973] 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 faces 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 forms a unit sphere,  which is topologically 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 degreees of freedom. Thus if we divide up the tangent space into cells according to which face each tangent touches, we get low 
dimensional cells corresponding to high dimensional faces and vice versa. If we performed this cell decomposition of the space of tangents for a single line segment, we would get just two full-dimensional cells (corresponding to tangents that touch only one of the two endpoints of the segment) separated by a hyperplane (corresponding to tangents containing the whole segment). But the cell decomposition corresponding to a Minkowski sum can be found by overlaying the decompositions for each subset in the sum, so the cell division corresponding to a zonotope is just the arrangement formed by overlaying some hyperplanes, and the faces of the zonotope correspond one-for-one with cells in this arrangement.

Because of this correspondence, we can construct zonotopes in the same amount of time it takes to construct these hyperplane arrangements, 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 generated by n vectors. However our implementation uses a slower algorithm better suited to the functional nature of Mathematica programming. We first find subsets of vectors corresponding to each face of the zonotope, by adding one vector at a time to the set of generators. Each new vector is combined with any previously computed faces with which it is parallel, and new faces are formed for each (d-1)-tuple of vectors not found in previous faces. Once we have generated all faces, we determine coordinates for their vertices recursively (each face is a lower-dimensional zonotope) and lift them into place by adding appropriate subsets of 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; by choosing transcendental points on the curve we also (hopefully) end up independent of the zonotope generators without blowing up the coordinates too much.

ZSignTest[vv_,f_] :=
	Det [ Part[vv,f] ~Join~
		  Table[(i+Pi)^j,
				{i,Length[vv[[1]]]-Length[f]},
				{j,Length[vv[[1]]]}]]//N;

Face Generation Stage

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) ||
		Chop[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]}]]

Face Placement Stage

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

Main Zonohedron Code

Zonotope[vv_,d_] :=
	ZLiftAll[vv,ZAllFaces[vv,d],d]

The general zonotope code will produce a recursive description in which 2-dimensional faces are lists of 1-dimensionald edges, etc.  For nice drawings of zonohedra we need to convert these lists of edges into a single polygon.

ZvEq[u_,v_] := Chop[Plus @@ (Abs /@ (u-v))] == 0

ZNext[f_,e_] :=
	Join @@ Map[
		If[ e[[2]] ~ZvEq~ #[[1]] &&
					Not[e[[1]] ~ZvEq~ #[[2]]], #,
			If[ e[[2]] ~ZvEq~ #[[2]] &&
					Not[e[[1]] ~ZvEq~ #[[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]

Examples

The Cube

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 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. The long diagonals of the rhombic dodecahedron's faces form an octahedron, while the short diagonals form a cube.

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 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 Truncated Rhombic Dodecahedron

This has as its generators the seven axes of symmetry of a tetrahedron. Since its generators are the union of those for the cube and the rhombic dodecahedron, it is the Minkowski sum of those two shapes.  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 Cuboctahedron

Since its generators are the union of those for the cube and the truncated octahedron, this is the Minkowski sum of those two shapes. But its generators can also be partitioned into three sets of three mutually orthogonal vectors, showing that this shape is also the Minkowski sum of three cubes. It is also known as the Great Rhombicuboctahedron. It can be combined with cubes and truncated octahedra in a regular space-filling pattern.

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 Small Rhombicuboctahedron

This is the Minkowski sum of a cube, a truncated octahedron, and a rhombic dodecahedron.  It has as its generators the 13 axes of symmetry of a cube. 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. The long diagonals of its faces form an icosihedron, and the short diagonals of its faces form a dodecahedron.

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

A Large Icosihedral Zonohedron

I found this lovely zonohedron on George Hart's "zonohedrification" web page [Hart 1996]. Its generators are the 31 axes of symmetry of the icosihedron.

Zonohedron[
({{1,0,-GoldenRatio},{1,0,GoldenRatio},
{0,-GoldenRatio,1},{0,GoldenRatio,1},
{-GoldenRatio,1,0},{GoldenRatio,1,0}}/Sqrt[GoldenRatio+2])
~Join~
({{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}}/2)
~Join~
({{1, GoldenRatio+1, 0},{-1,GoldenRatio+1,0},
{0, 1, GoldenRatio+1},{0,-1,GoldenRatio+1},
{GoldenRatio+1, 0, 1},{GoldenRatio+1,0,-1},
{GoldenRatio,GoldenRatio,GoldenRatio},
{GoldenRatio,GoldenRatio,-GoldenRatio},
{GoldenRatio,-GoldenRatio,GoldenRatio},
{GoldenRatio,-GoldenRatio,-GoldenRatio}}/
(Sqrt[3] GoldenRatio))]

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 [Bern, Eppstein, Guibas, Hersberger, Suri, and Wolter 1995] 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 [Ziegler 1995].  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}

References

Bern, M., Eppstein, D.,  Guibas, L., Hershberger, J., Suri, S. and Wolter, J.,
    The Centroid of Points with Approximate Weights. Proc. 3rd Eur. Symp. Algorithms,
    Lecture Notes in Computer Science 979, Springer, 1995, pp. 460-472.

Coxeter, H. S. M.,  Regular Polytopes. Dover, 1973, pp. 27-30.

D. Eppstein, D.,  The Geometry Junkyard: Zonohedra and Zonotopes.
    http://www.ics.uci.edu/~eppstein/junkyard/zono.html, 1997.

Hart, G. Zonohedrification.
    http://www.li.net/~george/virtual-polyhedra/zonohedrification.html, 1996.

Heckbert, P., An Efficient Algorithm for Generating Zonohedra.
    Tech. Rep. 11, NYIT Computer Graphics Lab, Feb. 1985.

Wells, D., The Penguin Dictionary of Curious and Interesting Geometry.
    Penguin, 1995, pp. 274-275.

R. Towle, R.,  Polar Zonohedra. The Mathematica J. 6(2), 1996, pp. 8-12.

Ziegler, G., Lectures on Polytopes. Springer, 1995, pp. 198-208.

ABOUT THE AUTHOR

ELECTRONIC SUBSCRIPTIONS