Go backward to 1 Vertex Enumeration
Go up to 2 Coordinate Descriptions
Go forward to 3 Polytope Verification
|
Go backward to 1 Vertex Enumeration Go up to 2 Coordinate Descriptions Go forward to 3 Polytope Verification |
XHTML 1.0 |
| 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. |
| Related problems: | 1, 3, 5 |
|---|
|
|
Why are some symbols not displayed correctly? |