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(n^{2}) sides.

Edelsbrunner [Algorithms in Combinatorial Geometry, Springer, 1987] writes
``it is very instructive to visualize the inductive construction
of a zonotope''.
To add the *i*th 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 *i*th 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(n^{d-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: .