Title: 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$.
Publication Year: 2016
Publication Date: 2016-05-23
Language: en
Type: preprint
Access and Citation
Cited By Count: 1
AI Researcher Chatbot
Get quick answers to your questions about the article from our AI researcher chatbot