| Input: | Polytope P of dimension d, positive integer 1 £ j £ d |
|---|---|
| Output: | A j-simplex contained in (containing) P of largest (smallest) volume |
| Status (general): | NP-hard |
|---|---|
| Status (fixed dim.): | Polynomial time |
|
Among the j-simplices of largest volume contained in P, there
is one whose vertices are vertices of P. Hence, one can restrict
attention to (j+1)-subsets of the vertices of P.
Gritzmann, Klee, and Larman [28] prove NP-hardness of the problem to find a largest j-simplex contained in a d-polytope P, where P is either given by a V-description or by an H-description and j is part of the input. The corresponding decision problems to decide whether there exists a j-simplex whose squared volume is larger than a given K are in NP(see [28]). Gritzmann et al. also prove that the case where j = d is strongly NP-hard if P is given by a V-description. Packer [51] additionally proves that this case is NP-hard if P is given by an H-description. If j is fixed and P is given by a V-description, the problem is solvable in polynomial time. However, if P is given by an H-description the problem is NP-hard for each fixed 1 £ j £ d, see [28]. If d is fixed, the problem to find a largest j-simplex is solvable in polynomial time: if P is given by an V-description we can enumerate all j-simplices in polynomial time and if P is given by an H-description we can first enumerate all vertices and then all j-simplices. Packer [51] also proves that the corresponding problem to find a d-simplex of smallest volume containing P is NP-hard, where P is either given by V- or H-description. It is unknown whether the decision problems for the squared volume of j-simplices containing P are in NP, cf. [51]. |