User: Guest  Login
Document type:
Zeitschriftenaufsatz 
Author(s):
Kulmburg, Adrian; Althoff, Matthias 
Title:
On the co-NP-Completeness of the Zonotope 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 optim...    »
 
Keywords:
zonotope; containment problem; zonotope norm; zonotope in zonotope; computational complexity; computational geometry; optimization 
Journal title:
European Journal of Control 
Year:
2021 
Language:
en 
Publisher:
Elsevier BV 
E-ISSN:
0947-3580 
Accepted:
25.06.2021