Zonotope

A zonotope is a Minkowski sum of finitely many line segments. For vectors , , ..., in , a zonotope can be written, up to a translation, as

Thus it is an image of the hypercube under an affine transformation. In particular, every linear transformation of a zonotope is again a zonotope, since it maps each generating line segment to a line segment or a point. The faces parallel to each generating vector form a so-called zone wrapping around the polytope (Eppstein 1996).

A three-dimensional zonotope is called a zonohedron.

There is some confusion in the definition of zonotopes (Eppstein 1996). Wells (1991, pp. 274-275) requires every -tuple of the generating vectors to span the whole space, so that all the proper faces of the zonotope are parallelotopes. Others (Bern et al. 1995; Ziegler 1995, pp. 198-208; Eppstein 1996) do not make this restriction. Coxeter (1973) starts with one definition but soon switches to the other.

For a full-dimensional zonotope, consider the hyperplane arrangement whose hyperplanes pass through the origin and are perpendicular to its nonzero generating vectors. Each region in the complement of these hyperplanes corresponds to a vertex of the zonotope. Intersecting the arrangement with the unit hypersphere gives a description in one fewer dimension (Eppstein 1996).

Matrices with bounded entries give a useful application (Trott 2006). For a matrix , let be its row sums, its column sums, , and . The map is a linear transformation. As the entries range over , the attainable sum vectors therefore form a zonotope in . Its dimension is 7, and it satisfies . Quantifier elimination removes the nine entries from the defining equations and bounds to obtain conditions on the eight sums. Trott (2006) instead uses strict bounds , which exclude some boundary sum vectors.

A planar example uses three real variables , , and in . The linear transformation has the hexagon

as its image. To obtain these inequalities, write and . The three intervals , , and have a common point iff all their lower bounds are at most all their upper bounds, exactly the comparisons produced by Fourier-Motzkin elimination.