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

DOI10.1007/BF02574058zbMath0826.52014OpenAlexW2000646287MaRDI QIDQ1892425

Peter Gritzmann, Victor Klee, David G. Larman

Publication date: 2 July 1995

Published in: Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://eudml.org/doc/131376

zbMATH Keywords

computational complexitypolytopesinscribed simpliceslargest simplices

Mathematics Subject Classification ID

(n)-dimensional polytopes (52B11) Computational aspects related to convexity (52B55) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Convex sets in (n) dimensions (including convex hypersurfaces) (52A20)

Related Items

On the complexity of some basic problems in computational convexity. I. Containment problems, Parameterized complexity and improved inapproximability for computing the largest \(j\)-simplex in a \(V\)-polytope, Largest \(j\)-simplices in \(d\)-cubes: Some relatives of the Hadamard maximum determinant problem, Exponential inapproximability of selecting a maximum volume sub-matrix, Polynomial-time approximation of largest simplices in \(V\)-polytopes., Turning Big Data Into Tiny Data: Constant-Size Coresets for $k$-Means, PCA, and Projective Clustering, What is known about unit cubes, Sum of Squares Certificates for Containment of $\mathcal{H}$-Polytopes in $\mathcal{V}$-Polytopes, Approximation of convex sets by polytopes, Subdeterminant Maximization via Nonconvex Relaxations and Anti-Concentration, On maximum volume submatrices and cross approximation for symmetric semidefinite and diagonally dominant matrices, SISAL Revisited

Cites Work

• Diameter, width, closest line pair, and parametric searching
• Deciding uniqueness in norm maximazation
• Computational complexity of norm-maximization
• A new polynomial-time algorithm for linear programming
• Some new results on smoothness and rotundity in normed linear spaces
• Geometric algorithms and combinatorial optimization
• Die meisten konvexen Körper sind glatt, aber nicht zu glatt
• The NP-completeness of the Hamiltonian cycle problem in planar digraphs with degree bound two
• On the complexity of some basic problems in computational convexity. I. Containment problems
• A random polynomial time algorithm for well-routing convex bodies
• Applications of random sampling in computational geometry. II
• Largest \(j\)-simplices in \(d\)-cubes: Some relatives of the Hadamard maximum determinant problem
• Computational complexity of inner and outer \(j\)-radii of polytopes in finite-dimensional normed spaces
• The content of some extreme simplexes
• On recognizing integer polyhedra
• Finding the smallest triangles containing a given convex polygon
• Hard Enumeration Problems in Geometry and Combinatorics
• An optimal algorithm for finding minimal enclosing triangles
• Polynomial algorithms in linear programming
• A PARALLEL ALGORITHM FOR ENCLOSED AND ENCLOSING TRIANGLES
• On The Complexity of Computing Mixed Volumes
• On maximal simplices inscribed in a central convex set
• Reducibility among Combinatorial Problems
• The complexity of satisfiability problems
• The maximum numbers of faces of a convex polytope
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item