Zonotope Construction via Shephard's Theorem

Requires a Wolfram Notebook System

Interact on desktop, mobile and cloud with the free Wolfram CDF Player or other Wolfram Language products.

Requires a Wolfram Notebook System

Edit on desktop, mobile and cloud with any Wolfram Language product.

Given , a set of generators for , the zonotope generated by is the convex hull of all vectors of the form ,; that is, is the Minkowski sum of all segments , where . Also, is the shadow of the -dimensional cube via the projection .

[more]

Given any such that is a basis of and , the Minkowski sum is called a parallelepiped. The zonotope is said to be paved by a collection of parallelepipeds whenever and is at most -dimensional for .

Shephard's theorem explicitly provides a recursively generated collection of vectors such that is a paving of . Each tile of this paving (i.e. each parallelepiped of the form ) is shown in the figure in a different color.

[less]

Contributed by: Lorenzo Dello Schiavo (September 2014)
Open content licensed under CC BY-NC-SA


Snapshots


Details

The 3D sample shows inductive construction via Shephard's algorithm of a zonohedron (a 3D zonotope) generated by a set of eight vectors spanning ; the paving results in 49 different parallelepipeds corresponding to the 49 different bases of , which may be extracted from the set.

The 2D sample shows an analogous construction of a zonotope generated by a set of nine vectors spanning ; the paving results in 36 different parallelepipeds.

Raw data is a matrix representation (by columns) of the parallelepipeds in each paving, i.e. the first columns of each matrix form a basis of , while the last one is the corresponding vector found via Shephard's algorithm.

Permutation # allows a permutation the initial vectors' sets (both in 2D and 3D) in six different ways. Since the algorithm is order sensitive, any permutation of these sets produces a different rearrangement of the tiles, which are nonetheless always the same and pave the same zonotope, showing that the latter only depends on its generating set. The recursion property of the algorithm may be deduced by the connectedness of the partial pavings at each step.

Details of the construction and a complete proof of Shephard's theorem may be found in §2.3 of [1].

Reference

[1] C. De Concini and C. Procesi, Topics in Hyperplane Arrangements, Polytopes, and Box Splines, New York: Springer, 2010.



Feedback (field required)
Email (field required) Name
Occupation Organization
Note: Your message & contact information may be shared with the author of any specific Demonstration for which you give feedback.
Send