Go backward to 3 Polytope Verification Go up to 2 Coordinate Descriptions Go forward to 5 Face Lattice of Geometric Polytopes |
XHTML 1.0 |
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). |
Related problems: | 3 |
---|
Why are some symbols not displayed correctly? |