Rounding of Polytopes in the Real Number Model of Computation

Let 𝒜 be a set of m points in ℝⁿ. We show that the problem of (1 + ϵ)n-rounding of 𝒜, i.e., the problem of computing an ellipsoid E ⊆ ℝⁿ such that [(1 + ϵ)n]⁻¹E ⊆ conv. hull(𝒜) ⊆ E, can be solved in O(mn²(ϵ⁻¹ + ln n + ln ln m)) arithmetic operations and comparisons. This result implies that the problem of approximating the minimum volume ellipsoid circumscribed about 𝒜 can be solved in O(m^3.5 ln(mϵ⁻¹)) operations to a relative accuracy of ϵ in the volume. The latter bound also applies to the (1 + ϵ)n-rounding problem. Our bounds hold for the real number model of computation.