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

DOI10.1007/BF01581243zbMATH Open0784.90076MaRDI QIDQ2368077FDOQ2368077

Authors: Peter Gritzmann, Victor Klee 

Publication date: 22 August 1993

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

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\)

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)

Cites Work

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

Cited In (33)

• Deterministic and randomized polynomial‐time approximation of radii
• A Variable-Complexity Norm Maximization Problem
• Deciding uniqueness in norm maximazation
• Minimal containment under homothetics: a simple cutting plane approach
• Sharpening geometric inequalities using computable symmetry measures
• Complexity yardsticks for \(f\)-vectors of polytopes and spheres
• A semidefinite hierarchy for containment of spectrahedra
• Fitting enclosing cylinders to data in \(\mathbb R^n\)
• Intrinsic volumes and successive radii
• Fixed-parameter complexity and approximability of norm maximization
• Note on the computational complexity of \(j\)-radii of polytopes in \(\mathbb R^ n\)
• Parameterized complexity and improved inapproximability for computing the largest \(j\)-simplex in a \(V\)-polytope
• 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
• Radii minimal projections of polytopes and constrained optimization of symmetric polynomials
• Polynomial-time approximation of largest simplices in \(V\)-polytopes.
• 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
• Sum of squares certificates for containment of \(\mathcal{H}\)-polytopes in \(\mathcal{V}\)-polytopes
• Largest \(j\)-simplices in \(d\)-cubes: Some relatives of the Hadamard maximum determinant problem
• 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)