backup forward

Go backward to 3 Polytope Verification
Go up to 2 Coordinate Descriptions
Go forward to 5 Face Lattice of Geometric Polytopes
XHTML 1.0

4 Polytope Containment

Input: Polytope P given in H-description, polytope Q given in V-description
Output: "Yes" if P ⊆ Q, "No" otherwise
Status (general): coNP -complete
Status (fixed dim.): Polynomial time
Freund and Orlin [20] proved that this problem is coNP -complete. Note that the reverse question whether Q ⊆ P is trivial. The questions where either both P and Q are given in H-description or both in V-description can be solved by linear programming (Problem 25), see Eaves and Freund [17]. For fixed dimension, one can enumerate all vertices of P in polynomial time (see Problem 1) and compare the descriptions of P and Q (after removing redundant points).

backup forward Why are some symbols not displayed correctly?