Zonotopes are defined using the Minkowski sum of sets A and B in a d-dimensional vector space, which is the set {p + q | p in A and q in B}. A zonotope is a special kind of convex polytope formed by taking the Minkowski sum of a collection of line segments. Familiar examples of zonotopes include the cube (generated by three unit length segments at right angles to each other) the rhombic dodecahedron (generated by four segments), and the truncated octahedron (generated by six segments parallel to the edges of the octahedron). Paul Heckbert has constructed a more complicated zonohedron generated by 30 vectors in a circle. The figure above is similar to Heckbert's, but is generated by two sets of line segments, with the endpoints of the two sets forming two different circles. The segments on the larger circle determine the overall shape of the zonotope, while the segments on the smaller circle lead to the existence of the belt of narrow faces near the equator of the zonotope. If one cuts this zonotope by a plane, one gets a polygonal slice with Omega(n2) sides.
Edelsbrunner [Algorithms in Combinatorial Geometry, Springer, 1987] writes ``it is very instructive to visualize the inductive construction of a zonotope''. To add the ith segment z(i) to the Minkowski sum, we sweep the current zonotope parallel to z(i) and then take the swept volume as the new zonotope. If we assume that the ith segment runs ``north-south", this step enlarges the current zonotope by stretching its ``equator'', a belt of faces of dimensions up to d-2, into a ``zone'' of faces of dimensions up to d-1. Faces of zonotopes are themselves lower-dimensional zonotopes.
There is a nice connection between d-dimensional zonotopes and (d-1)-dimensional arrangements. We consider the space of unit normal vectors of hyperplanes tangent to the zonotope. The d-dimensional unit vectors form a sphere, equivalent to oriented projective (d-1)-space. Any given unit vector is normal to a unique hyperplane that touches the zonotope at some kind of face. One can swing a hyperplanes while keeping it tangent to a k-dimensional face, passing through a collection of angles with dimension (d-1-k); these angles form a cell in this projective space and the faces of the zonotope thus correspond to a dual cell decomposition of space. If there were only a single vector, this decomposition would be given by a single hyperplane (partitioning the tangents into those that touch the origin, those that touch the endpoint of the vector, and those parallel to the vector that touch both points). But the decomposition corresponding to a Minkowski sum is formed by overlaying the decompositions corresponding to the two summands, so the cell decomposition of the tangent space to a zonotope is exactly a hyperplane arrangement. In particular, a zone of faces parallel to a given vector corresponds exactly to a hyperplane.
Because of this correspondence, one can construct zonotopes in time O(nd-1). The figure above was constructed by a Mathematica package for 3-dimensional zonotopes (available in HTML, Mathematica notebook format, or as a postscript tech. report) that I wrote using a slower but simpler algorithm.
[From "The Centroid of Points with Approximate Weights". For more information on zonohedra, see the zonohedron page of The Geometry Junkyard. For even more festive views of the easter egg, see D. Fowler's MIER graphics warehouse.]
From the Geometry Junkyard,
computational
and recreational geometry.
David Eppstein,
Theory Group,
ICS,
UC Irvine.
Last update: .