| Input: | Polytope P in H-description |
|---|---|
| Output: | "Yes" if P not simple (degenerate), "No" otherwise |
| Status (general): | Strongly NP-complete |
|---|---|
| Status (fixed dim.): | Polynomial time |
|
Independently proved to be NP-complete in the papers of
Chandrasekaran, Kabadi, and Murty [11] and Dyer
[14]. Fukuda, Liebling, and Margot [22] proved
that the problem is strongly NP-complete. For fixed
dimension, one can enumerate all vertices in polynomial time (see
Problem 1) and check whether they are
simple or not. Bremner, Fukuda, and Marzetta [8] noted that if P is given in V-description the problem is polynomial time solvable: enumerate the edges (1-skeleton, see Problem 5) and apply the Lower Bound Theorem. Erickson [19] showed that in the worst case W(mé d/2ù -1 + m log m) sideness queries are required to test whether a polytope is simple. For odd d this matches the upper bound. A sideness query is a question of the following kind: given d+1 points p0, ..., pd in Rd, does p0 lie "above", "below", or on the oriented hyperplane determined by p1, p2, ..., pd. |
| Related problems: | 1, 5 |
|---|