John Ellipsoid and the Center of Mass of a Convex Body

Abstract

It is natural to ask whether the center of mass of a convex body $K\subset {\mathbb{R}}^n$ lies in its John ellipsoid $B_K$, i.e., in the maximal volume ellipsoid contained in $K$. This question is relevant to the efficiency of many algorithms for convex bodies. In this paper, we obtain an unexpected negative result. There exists a convex body $K\subset {\mathbb{R}}^n$ such that its center of mass does not lie in the John ellipsoid $B_K$ inflated $(1-C\sqrt{\frac{\log (n)}{n}})n$ times about the center of $B_K$. Moreover, there exists a polytope $P\subset {\mathbb{R}}^n$ with $O(n^2)$ facets whose center of mass is not contained in the John ellipsoid $B_P$ inflated $O(\frac{n}{\log (n)})$ times about the center of $B_P$.

arXiv commentIn the original version, we've shown that there exists a convex body $K\subset {\mathbb{R}}^n$ such that its center of mass does not lie in the John ellipsoid $B_K$ inflated $cn$ times about the center of $B_K$ for some universal constant $c>0$. This time we replaced the constant $cn$ by $(1-C\sqrt{\frac{\log (n)}{n}})n$ for some universal constant $C>0$, which is sharp since it cannot exceed $n$. arXiv admin note: text overlap with arXiv:1703.02173