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. 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.