The Shapes of Polyhedra

Let A be a real matrix of size (n + d + 1) × n. We assume that all n × n submatrices of A are nonsingular and define the condition number C = C(A) to be the ratio of the largest n × n subdeterminant of A to the smallest in absolute value. In addition we assume that there is a positive vector π such that πA = 0. This implies that for any b, the body K_b = {x∣Ax ≤ b} is bounded. Let f(A) be the number of subsets of the rows of A, of cardinality n + 1, for which a positive linear combination equals zero.

The Banach-Mazur distance Ρ(K_b, K_c) for a pair of nonempty full dimensional bodies K_b and K_c is defined as follows: let λ₁ be the smallest λ for which K_c ⊆ λ K_b + ξ¹ for some ξ¹ and λ₂ the smallest λ for which K_b ⊆ λ K_c + ξ² for some ξ². Then Ρ(K_b, K_c) = log(λ₁ ⋅ λ₂).

We show that for any ε > 0, there exists a subset of the bodies K_b, of cardinality not larger than f(A)⌈2 log₂ (nC)/ε⌉^d, such that every body is within distance ε from some member of the subset.