Two convex bodies $K$ and $L$ in $\mathbb{R}^n$ are affine-equivalent if there exists an affine transformation $T$ such that $T(K)=L$. To measure how close two convex bodies are when they are not exactly affinely equivalent, one introduces the Banach--Mazur distance. Roughly speaking, this is the smallest factor $R \ge 1$ such that, after an appropriate affine transformation, one body is contained in the other, and the other is contained in its dilation by $R$ (with respect to some center $\xi$).

A consequence of Fritz John’s theorem is that for any symmetric convex body, one can approximate $K$ by a polytope $P$ with $O(n)$ facets and Banach--Mazur distance $O(\sqrt{n})$, which is sharp for the Euclidean ball. In contrast, for general convex bodies, the same theorem implies that even with $O(n^2)$ facets, one can only guarantee distance $O(n)$. Thus, there is a gap of order $\sqrt{n}$ for Coarse Polytope Approximation (coarse means the allowance of facets/vertices can only be polynomial in $n$.)

While this problem has been known for over two decades, it remains open whether this $\sqrt{n}$ gap is essential (up to polylogarithmic factors).

In this talk, we will. show that the $O(n)$ bound is essential if one requires the scaling center to be a classical center, such as the barycenter. In other words, either the $\sqrt{n}$ gap is inherent for general convex bodies, or one must go beyond such classical choices of centers. We also include a concrete open problem that appears approachable with current technique is also included.

(This is joint work with Mark Rudelson.)