backup forward

Go backward to 1 Vertex Enumeration
Go up to 2 Coordinate Descriptions
Go forward to 3 Polytope Verification

2 Facet Enumeration

Input: Polytope P in V-description with n points
Output: Non-redundant H-description of P
Status (general): Open; polynomial total time if P is simple or simplicial
Status (fixed dim.): Polynomial time
In [1] it is shown that FACET ENUMERATION is strongly polynomially equivalent to Problem 3 and thus to Problem 1 (see the comments there).

For this problem, one can assume to have an interior point (e.g., the vertex barycenter). FACET ENUMERATION is sometimes called the convex hull problem.

backup forward Why are some symbols not displayed correctly?