# Finding the Boundary Faces of the Zonohedron

A zonotope is a linear combination of m vectors with coefficients in [0,1]: $Z = \{ \sum \lambda_i v_i : 0 \leq \lambda _i \leq 1 \}$. The fancy way is to say it's the Minkowski sum of line segments in Rn.

One step in a certain geometric construction is to find the boundary faces of a zonohedron (3D). The boundary points all have λ=0 or 1 but that requires finding 2m points. It's also not clear which ones are within the polygon and which ones are corners. It might be possible to do it faster inductively.

In two dimensions you can arrange the set $\{ v_i, -v_i: i = 1 \dots m\}$ in a circle and add them in clockwise order. In 3D, I might arrange the vectors in a sphere, but then I'm not sure in which order to add the vectors. I read somewhere, this is like integrating a discrete version of the Gauss map.

-

If you are looking for facets rather than vertices, the answer is easier to formulate in terms of flats of the corresponding matroid. Take the (n-1)-dim flats - each corresponds to 2 facets (one on each side). For vertices, the answer is easier to formulate in terms of oriented matroids. For more on zonotopes and connections to matroids, read here:

• A. Björner, M. Las Vergnas, B. Sturmfels, N. White, G. Ziegler, Oriented Matroids. Cambridge.

• Gunter M. Ziegler, Lectures on Polytopes, Springer.

-
Are there standard algorithms for enumerating flats in matroids? – j.c. Nov 4 '10 at 19:58

Computing the Minkowski sum in 2D and 3D is well studied, to the point where there is robust software as part of CGAL. Here is an impressive image from the CGAL manual on computing the Minkowski sum of 3D polyhedra:

I am less familiar with the computation in $\mathbb{R}^d$, but there is work, e.g., the 2010 paper, "Maximal f-vectors of Minkowski sums of large numbers of polytopes" by Christophe Weibel. This paper and its references may prove useful.

-