LARGEST J-SIMPLICES IN N-POLYTOPES

Relative to a given convex body C, a j-simplex S in C is largest if it has maximum volume (j-measure) among all j-simplices contained in C, and S is stable (resp. rigid) if vol(S) greater than or equal to vol(S ') (resp. vol(S) > vol(S')) for each j-simplex S' that is obtained fro m S by moving a single vertex of S to a new position in C. This paper contains a variety of qualitative results that are related to the prob lems of finding a largest, a stable, or a rigid j-simplex in a given n -dimensional convex body or convex polytope. In particular, the comput ational complexity of these problems is studied both for V-polytopes ( presented as the convex hull of a finite set of points) and for H-poly topes (presented as an intersection of finitely many half-spaces).