John Ellipsoid and the Center of Mass of a Convex Body

High Dimensional Seminar
Wednesday, September 19, 2018 - 12:55pm
1 hour (actually 50 minutes)
Skiles 006
University of Michigan
It is natural to question 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. 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-o(1))n$ times about the center of $B_K$. (Yet, if one inflate $B_K$ by a factor $n$, it contains $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$.