Go backward to 5 Face Lattice of Geometric PolytopesGo up to 2 Coordinate DescriptionsGo forward to 7 Number of Vertices |
XHTML 1.0 |

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 Erickson [19] showed that in the worst case
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 in p_{0}, …,
p_{d}, does R^{d} lie "above", "below",
or on the oriented hyperplane determined by p_{0}.
p_{1}, p_{2},
…, p_{d} |

Related problems: | 1, 5 |
---|

Why are some symbols not displayed correctly? |