backup

Go backward to 12 Volume
Go up to 2 Coordinate Descriptions
XHTML 1.0

13 Largest/Smallest j-Simplex

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].


backup Why are some symbols not displayed correctly?