On the co-NP-completeness of the zonotope containment problem. (November 2021) - Kulmburg, Adrian; Althoff, Matthias
Highlights: The zonotope containment problem is co-NP-complete. Disproving zonotope containment can easily be done using optimization. A non-degenerate zonotope induces a norm. Zonotope norms can be used to solve the point containment problem. Abstract: We introduce a new type of norm for non-degenerate zonotopes to solve the point containment problem, i.e., whether a point lies in a zonotope. With this norm we prove the co-NP-completeness of the zonotope containment problem, i.e., whether a zonotope is contained within another one. We propose novel algorithms to solve the zonotope containment problem exactly in polynomial time when fixing the dimension or the number of generators of either of the two zonotopes. In addition, we propose an optimisation-based algorithm, that is particularly suitable for disproving containment for zonotopes.