Go backward to 3 Polytope Verification
Go up to 2 Coordinate Descriptions
Go forward to 5 Face Lattice of Geometric Polytopes
|
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? |