On the co-NP-completeness of the zonotope containment problem. (November 2021)

• Record Type: Journal Article
• Authors: Kulmburg, Adrian; Althoff, Matthias
• Is Part Of: European journal of control. Volume 62(2021)
• Page Start: 84
• Page End: 91
• Publication Date: 2021-11
• Subjects: Zonotope -- Containment problem -- Zonotope norm -- Computational complexity -- Computational geometry -- Optimization; Control theory -- Periodicals; Automatic control -- Periodicals; Automatic control -- Mathematics -- Periodicals; Electronic journals; 629.805
• DOI: 10.1016/j.ejcon.2021.06.028
• Languages: English
• ISSNs: 0947-3580

Abstract

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.