5
$\begingroup$

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.

$\endgroup$

2 Answers 2

6
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Are there standard algorithms for enumerating flats in matroids? $\endgroup$
    – j.c.
    Nov 4, 2010 at 19:58
  • $\begingroup$ In particular, Theorem 2.2.2 of the first text ("Oriented Matroids") should answer your question. $\endgroup$ Aug 14, 2020 at 12:52
2
$\begingroup$

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:
Mink sum
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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.