backup forward

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 Ω(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.

backup forward Why are some symbols not displayed correctly?