Largest \(j\)-simplices in \(n\)-polytopes
A \(j\)-simplex \(S\) contained in an \(n\)-dimensional polytope \(C\) is largest if its \(j\)-measure is maximal among all such \(j\)-simplices. If, for every \(S'\) obtained by moving a single vertex of \(S\) within \(C\), \(\text{vol}(S) \geq \text{vol} (S')\), we call \(S\) stable; if the inequality is strict, we call \(S\) rigid. This paper contains many results on the existence, uniqueness, and computation of largest, stable, and rigid inscribed simplices. In some forms, problems such as that of computing a largest inscribed simplex can be solved in polynomial time; other forms of the same problems are shown to be NP-hard. The paper concludes with a large selection of open problems.
scientific article; zbMATH DE number 764240
scientific article