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

Peter Gritzmann, Victor Klee

Research output: Contribution to journalArticlepeer-review

29 Scopus citations

Abstract

This paper studies the complexity of computing (or approximating, or bounding) the various inner and outer radii of an n-dimensional convex polytope in the space ∝n equipped with an ℓp norm or a polytopal norm. The polytope P is assumed to be presented as the convex hull of finitely many points with rational coordinates (V-presented) or as the intersection of finitely many closed halfspaces defined by linear inequalities with rational coefficients (ℋ-presented). The inner j-radius of P is the radius of a largest j-ball contained in P; it is P's inradius when j = n and half of P's diameter when j = 1. The outer j-radius measures how well P can be approximated, in a minimax sense, by an (n - j)-flat; it is P's circumradius when j = n and half of P's width when j = 1. The binary (Turing machine) model of computation is employed. The primary concern is not with finding optimal algorithms, but with establishing polynomial-time computability or NP-hardness. Special attention is paid to the case in which P is centrally symmetric. When the dimension n is permitted to vary, the situation is roughly as follows: (a) for general ℋ-presented polytopes in ℓp spaces with 1<p<∞, all outer radius computations are NP-hard; (b) in the remaining cases (including symmetric ℋ-presented polytopes), some radius computations can be accomplished in polynomial time and others are NP-hard. These results are obtained by using a variety of tools from the geometry of convex bodies, from linear and nonlinear programming, and from the theory of computational complexity. Applications of the results to various problems in mathematical programming, computer science and other fields are included.

Original languageEnglish
Pages (from-to)163-213
Number of pages51
JournalMathematical Programming
Volume59
Issue number1-3
DOIs
StatePublished - Mar 1993
Externally publishedYes

Keywords

  • AMS subject Classifications: 90C30, 68Q15, 52A25, 90C05, 90C20, 90C25, 11J72, 11J81
  • Computational convexity
  • NP-hardness
  • breadth
  • circumsphere
  • computational complexity
  • computational geometry
  • convex body
  • convex hull
  • diameter
  • ellipsoid method
  • insphere
  • linear programming
  • mathematical programming
  • polarity
  • polynomial-time algorithms
  • polytope
  • quadratic programming
  • radius
  • robotics
  • sensitivity analysis
  • width

Fingerprint

Dive into the research topics of 'Computational complexity of inner and outer j-radii of polytopes in finite-dimensional normed spaces'. Together they form a unique fingerprint.

Cite this