Go backward to 4 Polytope Containment
Go up to 2 Coordinate Descriptions
Go forward to 6 Degeneracy Testing
|
Go backward to 4 Polytope Containment Go up to 2 Coordinate Descriptions Go forward to 6 Degeneracy Testing |
XHTML 1.0 |
| Input: | Polytope P in H-description |
|---|---|
| Output: | Hasse-diagram of the face lattice of P |
| Status (general): | Polynomial total time |
|---|---|
| Status (fixed dim.): | Polynomial time |
|
See comments on Problem 1. Many
algorithms for the VERTEX ENUMERATION PROBLEM in fact
compute the whole face lattice of the polytope.
Swart [62], analyzing an algorithm of Chand and
Kapur [10], proved that there exists a polynomial total
time algorithm for this problem. For a faster algorithm see
Seidel [58]. Fukuda, Liebling, and Margot [22]
gave an algorithm which uses working space (without space for the
output) bounded polynomially in the input size, but it has to
solve many linear programs.
For fixed dimension, the size of the output is polynomial in the size of the input; hence, a polynomial total time algorithm becomes a polynomial algorithm in this case. The complexity status of the analogue problem with the polytope specified by a V-description is the same. The problem of enumerating the k-skeleton of P seems to be open, even if k is fixed. Note that, for fixed k, the latter problem can be solved by linear programming (Problem 25) in polynomial time if the polytope is given in V-description rather than in H-description. |
| Related problems: | 1, 2, 3, 14, 15 |
|---|
|
|
Why are some symbols not displayed correctly? |