Go backward to 4 Polytope ContainmentGo up to 2 Coordinate DescriptionsGo 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 The problem of enumerating the |

Related problems: | 1, 2, 3, 14, 15 |
---|

Why are some symbols not displayed correctly? |