Go backward to 5 Face Lattice of Geometric Polytopes
Go up to 2 Coordinate Descriptions
Go forward to 7 Number of Vertices

6 Degeneracy Testing

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.