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

DOI10.1007/BF01581243MaRDI QIDQ2368077zbMATH OpenFDO

Authors Peter Gritzmann, Victor Klee

Publication date 22 August 1993

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

zbMATH Keywords

sensitivity analysiscomputational geometryconvex bodydiameterpolytopeNP-hardnessradiuspolynomial-time algorithmswidthellipsoid methodpolaritycircumsphereinsphere\(n\)-dimensional convex polytopebreadth,

Mathematics Subject Classification ID

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

Recommendations

• Note on the computational complexity of \(j\)-radii of polytopes in \(\mathbb R^ n\)
• Inner and outer \(j\)-radii of convex bodies in finite-dimensional normed spaces
• scientific article; zbMATH DE number 1560333
• Geometric optimization problems likely not contained in \(\mathbb A\mathbb P\mathbb X\)

Cites work

• scientific article; zbMATH DE number 3858224 (Why is no real title available?)
• scientific article; zbMATH DE number 3876377 (Why is no real title available?)
• scientific article; zbMATH DE number 3877692 (Why is no real title available?)
• scientific article; zbMATH DE number 4200003 (Why is no real title available?)
• scientific article; zbMATH DE number 3919830 (Why is no real title available?)
• scientific article; zbMATH DE number 3980484 (Why is no real title available?)
• scientific article; zbMATH DE number 4032498 (Why is no real title available?)
• scientific article; zbMATH DE number 3677572 (Why is no real title available?)
• scientific article; zbMATH DE number 37080 (Why is no real title available?)
• scientific article; zbMATH DE number 3511563 (Why is no real title available?)
• scientific article; zbMATH DE number 3594676 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 665697 (Why is no real title available?)
• scientific article; zbMATH DE number 3793772 (Why is no real title available?)
• scientific article; zbMATH DE number 3804333 (Why is no real title available?)
• scientific article; zbMATH DE number 3894826 (Why is no real title available?)
• scientific article; zbMATH DE number 3314644 (Why is no real title available?)
• A new polynomial-time algorithm for linear programming
• Computational complexity of norm-maximization
• Computing the width of a set
• DIAMETERS OF SETS IN FUNCTION SPACES AND THE THEORY OF BEST APPROXIMATIONS
• Finding the convex hull facet by facet
• Geometric algorithms and combinatorial optimization
• Good and Bad Radii of Convex Polygons
• Inner and outer \(j\)-radii of convex bodies in finite-dimensional normed spaces
• Linear-Time Algorithms for Linear Programming in $R^3 $ and Related Problems
• On the complexity of four polyhedral set containment problems
• On the complexity of some geometric problems in unbounded dimension
• Optimal scaling of balls and polyhedra
• Polygonal approximation by the minimax method
• Polynomial algorithms in linear programming
• The Complexity of Vertex Enumeration Methods
• The Minimum Covering Sphere Problem
• The Width of a Chair
• The complexity of satisfiability problems
• The complexity of theorem-proving procedures
• The maximum numbers of faces of a convex polytope

Cited in

(33)

• Deciding uniqueness in norm maximazation
• Minimal containment under homothetics: a simple cutting plane approach
• A Variable-Complexity Norm Maximization Problem
• Deterministic and randomized polynomial‐time approximation of radii
• Complexity yardsticks for \(f\)-vectors of polytopes and spheres
• Sharpening geometric inequalities using computable symmetry measures
• A semidefinite hierarchy for containment of spectrahedra
• Fitting enclosing cylinders to data in \(\mathbb R^n\)
• Intrinsic volumes and successive radii
• Parameterized complexity and improved inapproximability for computing the largest \(j\)-simplex in a \(V\)-polytope
• Note on the computational complexity of \(j\)-radii of polytopes in \(\mathbb R^ n\)
• Fixed-parameter complexity and approximability of norm maximization
• Successive radii and ball operators in generalized Minkowski spaces
• Geometric optimization problems likely not contained in \(\mathbb A\mathbb P\mathbb X\)
• A note on approximation of a ball by polytopes
• Polynomial-time approximation of largest simplices in \(V\)-polytopes.
• 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
• Largest \(j\)-simplices in \(n\)-polytopes
• On computing the diameter of a point set in high dimensional Euclidean space.
• Inner and outer \(j\)-radii of convex bodies in finite-dimensional normed spaces
• Computational complexity of norm-maximization
• Computing the discrete compactness of orthogonal pseudo-polytopes via their \(n\)D-EVM representation
• Largest \(j\)-simplices in \(d\)-cubes: Some relatives of the Hadamard maximum determinant problem
• Sum of squares certificates for containment of \(\mathcal{H}\)-polytopes in \(\mathcal{V}\)-polytopes
• Inner and outer approximations of polytopes using boxes.
• The analysis and the representation of balanced complex polytopes in 2D
• Diversities and the generalized circumradius
• On clustering bodies: geometry and polyhedral approximation
• Successive radii and Minkowski addition
• No dimension-independent core-sets for containment under homothetics
• APPROXIMATING SMALLEST ENCLOSING BALLS WITH APPLICATIONS TO MACHINE LEARNING
• Efficient subspace approximation algorithms

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2368077)