Largest \(j\)-simplices in \(n\)-polytopes (Q1892425)

From MaRDI portal
scientific article
Language Label Description Also known as
English
Largest \(j\)-simplices in \(n\)-polytopes
scientific article

    Statements

    Largest \(j\)-simplices in \(n\)-polytopes (English)
    0 references
    0 references
    0 references
    0 references
    0 references
    2 July 1995
    0 references
    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.
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    polytopes
    0 references
    largest simplices
    0 references
    computational complexity
    0 references
    inscribed simplices
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references