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

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