AProPo -- 5 Face Lattice of Geometric Polytopes

Go backward to 4 Polytope Containment
Go up to 2 Coordinate Descriptions
Go forward to 6 Degeneracy Testing

5 Face Lattice of Geometric Polytopes

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.