Computational complexity of inner and outer \(j\)-radii of polytopes in finite-dimensional normed spaces

DOI10.1007/BF01581243zbMath0784.90076MaRDI QIDQ2368077

Victor Klee, Peter Gritzmann

Publication date: 22 August 1993

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

zbMATH Keywords

sensitivity analysiswidthdiameterpolytopeconvex bodyradiuscomputational geometryNP-hardnesspolaritypolynomial-time algorithmsellipsoid methodcircumsphereinsphere\(n\)-dimensional convex polytopebreadth,

Mathematics Subject Classification ID

Convex programming (90C25) (n)-dimensional polytopes (52B11) Abstract computational complexity for mathematical programming problems (90C60) Nonlinear programming (90C30) Quadratic programming (90C20) Linear programming (90C05)

Related Items (27)

Largest \(j\)-simplices in \(n\)-polytopes ⋮ A note on approximation of a ball by polytopes ⋮ Fitting enclosing cylinders to data in \(\mathbb R^n\) ⋮ SHARPENING GEOMETRIC INEQUALITIES USING COMPUTABLE SYMMETRY MEASURES ⋮ Note on the computational complexity of \(j\)-radii of polytopes in \(\mathbb R^ n\) ⋮ On clustering bodies: geometry and polyhedral approximation ⋮ Largest \(j\)-simplices in \(d\)-cubes: Some relatives of the Hadamard maximum determinant problem ⋮ Diversities and the generalized circumradius ⋮ No dimension-independent core-sets for containment under homothetics ⋮ Successive radii and Minkowski addition ⋮ Successive radii and ball operators in generalized Minkowski spaces ⋮ Polynomial-time approximation of largest simplices in \(V\)-polytopes. ⋮ Intrinsic volumes and successive radii ⋮ Inner and outer approximations of polytopes using boxes. ⋮ Efficient subspace approximation algorithms ⋮ Inner and outer \(j\)-radii of convex bodies in finite-dimensional normed spaces ⋮ Deciding uniqueness in norm maximazation ⋮ Minimal containment under homothetics: a simple cutting plane approach ⋮ Deterministic and randomized polynomial‐time approximation of radii ⋮ Sum of Squares Certificates for Containment of $\mathcal{H}$-Polytopes in $\mathcal{V}$-Polytopes ⋮ Computational complexity of norm-maximization ⋮ APPROXIMATING SMALLEST ENCLOSING BALLS WITH APPLICATIONS TO MACHINE LEARNING ⋮ Radii minimal projections of polytopes and constrained optimization of symmetric polynomials ⋮ Calculus of fuzzy vector-valued functions and almost periodic fuzzy vector-valued functions on time scales ⋮ A Semidefinite Hierarchy for Containment of Spectrahedra ⋮ Fixed-parameter complexity and approximability of norm maximization ⋮ On computing the diameter of a point set in high dimensional Euclidean space.

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Computational complexity of norm-maximization
• A new polynomial-time algorithm for linear programming
• Inner and outer \(j\)-radii of convex bodies in finite-dimensional normed spaces
• Geometric algorithms and combinatorial optimization
• On the complexity of some geometric problems in unbounded dimension
• DIAMETERS OF SETS IN FUNCTION SPACES AND THE THEORY OF BEST APPROXIMATIONS
• The Complexity of Vertex Enumeration Methods
• Polygonal approximation by the minimax method
• Good and Bad Radii of Convex Polygons
• Linear-Time Algorithms for Linear Programming in $R^3 $ and Related Problems
• Finding the convex hull facet by facet
• On the complexity of four polyhedral set containment problems
• Computing the width of a set
• Polynomial algorithms in linear programming
• Optimal scaling of balls and polyhedra
• The Width of a Chair
• The complexity of satisfiability problems
• The maximum numbers of faces of a convex polytope
• The Minimum Covering Sphere Problem
• The complexity of theorem-proving procedures

This page was built for publication: Computational complexity of inner and outer \(j\)-radii of polytopes in finite-dimensional normed spaces