Go up to 2 Coordinate DescriptionsGo forward to 2 Facet Enumeration |
XHTML 1.0 |

Input: | Polytope P in H-description |
---|---|

Output: | Non-redundant V-description of P |

Status (general): | Open; polynomial total time if P is simple or
simplicial |
---|---|

Status (fixed dim.): | Polynomial time |

Let d = dim(P) and let m be the number of inequalities in the
input. It is well known that the number of vertices n can be
exponential (Ω(m) in the size of
the input (e.g., Cartesian products of suitably chosen
two-dimensional polytopes and prisms over them).
^{⌊d/2⌋ })VERTEX ENUMERATION is strongly polynomially equivalent to Problem 3 (see Avis, Bremner, and Seidel [1]). Since Problem 2 is strongly polynomially equivalent to Problem 3 as well, VERTEX ENUMERATION is also strongly polynomially equivalent to Problem 2. For fixed n, e.g., an O(m log n + (m n)polylog^{1-1/(⌊d/2⌋ +1)} m) algorithm of Chan [9]. For general There are many more algorithms known for this problem - none of them is a polynomial total time algorithm for general polytopes. See the overview article of Seidel [59]. Most of these algorithms can be generalized to directly work for unbounded polyhedra, too. |

Related problems: | 2, 3, 5, 7 |
---|

Why are some symbols not displayed correctly? |