Largest j-simplices in n-polytopes

P. Gritzmann, V. Klee, D. Larman

Research output: Contribution to journalArticlepeer-review

39 Scopus citations

Abstract

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)≥vol(S′) (resp. vol(S)>vol(S′)) for each j-simplex S′ that is obtained from 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 problems of finding a largest, a stable, or a rigid j-simplex in a given n-dimensional convex body or convex polytope. In particular, the computational complexity of these problems is studied both for[Figure not available: see fulltext.]-polytopes (presented as the convex hull of a finite set of points) and for ℋ-polytopes (presented as an intersection of finitely many half-spaces).

Original languageEnglish
Pages (from-to)477-515
Number of pages39
JournalDiscrete and Computational Geometry
Volume13
Issue number1
DOIs
StatePublished - Dec 1995
Externally publishedYes

Fingerprint

Dive into the research topics of 'Largest j-simplices in n-polytopes'. Together they form a unique fingerprint.

Cite this