Largest \(j\)-simplices in \(n\)-polytopes
type: Item
instance of: scholarly article
title: Largest \(j\)-simplices in \(n\)-polytopes
zbMATH Open document ID: 0826.52014
DOI: 10.1007/BF02574058
author: Peter Gritzmann
author: Victor Klee
author: D. G. Larman
published in: Discrete \& Computational Geometry
publication date: 1995-07-02T00:00:00Z
full work available at URL: https://eudml.org/doc/131376
review text: 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.
Mathematics Subject Classification ID: 52B55
Mathematics Subject Classification ID: 68W25
Mathematics Subject Classification ID: 68Q17
Mathematics Subject Classification ID: 52B11
Mathematics Subject Classification ID: 52A20
zbMATH DE Number: 764240
zbMATH Keywords: polytopes
zbMATH Keywords: largest simplices
zbMATH Keywords: computational complexity
zbMATH Keywords: inscribed simplices
reviewed by: Robert Dawson
MaRDI profile type: Publication
cites work: Q5818996
cites work: Computational complexity of norm-maximization
cites work: A PARALLEL ALGORITHM FOR ENCLOSED AND ENCLOSING TRIANGLES
cites work: Diameter, width, closest line pair, and parametric searching
cites work: Applications of random sampling in computational geometry. II
cites work: Q3976408
cites work: On The Complexity of Computing Mixed Volumes
cites work: A random polynomial time algorithm for well-routing convex bodies
cites work: Q5344631
cites work: Q4198056
cites work: Deciding uniqueness in norm maximazation
cites work: Computational complexity of inner and outer \(j\)-radii of polytopes in finite-dimensional normed spaces
cites work: On the complexity of some basic problems in computational convexity. I. Containment problems
cites work: Q4309969
cites work: Geometric algorithms and combinatorial optimization
cites work: Die meisten konvexen Körper sind glatt, aber nicht zu glatt
cites work: Q5547252
cites work: Largest \(j\)-simplices in \(d\)-cubes: Some relatives of the Hadamard maximum determinant problem
cites work: Q4385525
cites work: A new polynomial-time algorithm for linear programming
cites work: Reducibility among Combinatorial Problems
cites work: Polynomial algorithms in linear programming
cites work: Some new results on smoothness and rotundity in normed linear spaces
cites work: Q3338862
cites work: Finding the smallest triangles containing a given convex polygon
cites work: Hard Enumeration Problems in Geometry and Combinatorics
cites work: Q5804679
cites work: On maximal simplices inscribed in a central convex set
cites work: The maximum numbers of faces of a convex polytope
cites work: An optimal algorithm for finding minimal enclosing triangles
cites work: Q4146536
cites work: On recognizing integer polyhedra
cites work: The NP-completeness of the Hamiltonian cycle problem in planar digraphs with degree bound two
cites work: The complexity of satisfiability problems
cites work: The content of some extreme simplexes
OpenAlex ID: W2000646287
description: scientific article; zbMATH DE number 764240