2019/10/16 by Kochdumper, Niklas, Althoff, Matthias
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1910.07271
We prove that each bounded polytope can be represented as a polynomial zonotope, which we refer to as the Z-representation of polytopes. Previous representations are the vertex representation (V-representation) and the halfspace representation (H-representation). Depending on the polytope, the Z-representation can be more compact than the V-representation and the H-representation. In addition, the Z-representation enables the computation of linear maps, Minkowski addition, and convex hull with a computational complexity that is polynomial in the representation size. The usefulness of the new representation is demonstrated by range bounding within polytopes.