On the co-NP-Completeness of the Zonotope Containment Problem
| Autor: | Adrian Kulmburg, Matthias Althoff |
|---|---|
| Jazyk: | angličtina |
| Rok vydání: | 2020 |
| Předmět: |
0209 industrial biotechnology
Containment (computer programming) Mathematics::Combinatorics 021103 operations research Mathematics::Commutative Algebra Computer science Dimension (graph theory) 0211 other engineering and technologies General Engineering 02 engineering and technology Type (model theory) co-NP ddc Combinatorics 020901 industrial engineering & automation Norm (mathematics) Mathematics::Metric Geometry Point (geometry) Completeness (statistics) zonotope containment problem zonotope norm zonotope in zonotope computational complexity computational geometry optimization justITSELF Time complexity |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|