Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
add comment

2 Answers

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.

share|improve this answer
    
Are there standard algorithms for enumerating flats in matroids? –  j.c. Nov 4 '10 at 19:58
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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