Linear Encodings for Polytope Containment Problems

The polytope containment problem is deciding whether a polytope is a contained within another polytope. The complexity heavily depends on how the polytopes are represented. While there exists efficient necessary and sufficient conditions for polytope containment when their hyperplanes are available (H-polytopes), the case when polytopes are represented by affine transformations of H-polytopes, which we refer to as AH-polytopes, is known to be co-NP-complete. In this paper, we provide a sufficient condition for AH-polytope in AHpolytope problem that can be cast as a linear set of constraints with size that grows linearly with the number of hyperplanes of each polytope. These efficient encodings enable us to designate certain components of polytopes as decision variables, and incorporate them into a convex optimization problem. We present the usefulness of our results on applications to the zonotope containment problem, computing polytopic Hausdorff distances, and finding inner approximations to orthogonal projections of polytopes. Illustrative examples are included.