Small primitive zonotopes (Q1740472)

The zonotope generated by a set of vectors $G$ is the convex hull of the signed sums of all elements of $G$. For example, the cube $[-1,1]^3$ is a zonotope and is generated by the standard basis vectors. This article focuses on the primitive zonotopes, denoted by $Z_q(d,p)$ for positive integers $d,p,q$ or $q = \infty$, which are the zonotopes generated by the primitive integer vectors $v$ satisfying $\Vert v \Vert_q \leq p$. The authors also consider the \textit{positive primitive zonotopes}, denoted by $Z^+_q(d,p)$, which is defined the same as $Z_q(d,p)$ with the exception that all vectors must have nonnegative coordinates. \par This article examines the diameter of and linear optimization over primitive zonotopes. Section 2 recalls results surrounding zonotopes and their diameters, as well as matroid optimization. In Section 3, the authors collect information for primitive zonotopes where $d$ and $p$ are small, such as the number of vertices and the diameter, with this information organized into tables. The following section discusses the complexity of linear optimization over primitive zonotopes. Namely, conditions are provided in which extremality, adjacency, and separation are solvable in polynomial time. The final section provides the proofs for results stated in sections 2 and 3. For the entire collection see [Zbl 1400.52002].