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 \(\bigl (1-C\sqrt{\frac{\log (n)}{n}}\bigr )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\bigl (\frac{n}{\log (n)}\bigr )\) times about the center of \(B_P\).
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Artstein-Avidan, S., Giannopoulos, A.A., Milman, V.D.: Asymptotic Geometric Analysis. Part I. Mathematical Surveys and Monographs, vol. 202. American Mathematical Society, Providence (2015)
Çinlar, E.: Probability and Stochastics. Graduate Texts in Mathematics, vol. 261. Springer, New York (2011)
Fradelizi, M., Paouris, G., Schütt, C.: Simplices in the Euclidean ball. Can. Math. Bull. 55(3), 498–508 (2012)
John, F.: Extremum problems with inequalities as subsidiary conditions. Studies and Essays Presented to R. Courant on his 60th Birthday, pp. 187–204. Interscience, New York (1948)
Khachiyan, L.G.: Rounding of polytopes in the real number model of computation. Math. Oper. Res. 21(2), 307–320 (1996)
Latała, R.: On the equivalence between geometric and arithmetic means for log-concave measures. Convex Geometric Analysis. Mathematical Sciences Research Institute Publications, vol. 34, pp. 123–127. Cambridge University Press, Cambridge (1999)
Lee, Y.T., Sidford, A.: Efficient inverse maintenance and faster algorithms for linear programming. In: Proceedings of the 56th IEEE Annual Symposium on Foundations of Computer Science (FOCS’15), pp. 18–20. IEEE, Washington, DC (2015)
Milman, V.D., Schechtman, G.: Asymptotic theory of finite-dimensional normed spaces. With an appendix by M. Gromov. Lecture Notes in Mathematics, vol. 1200. Springer, Berlin (1986)
Acknowledgements
I thank my advisor, Professor Mark Rudelson, for discussing and providing advice about this problem. I am also thankful Professor Santosh Vempala who identified the problem and explained the corresponding computer science background. Moreover, I would like to express my thanks to the anonymous referee for her/his suggestion on the improvement of the result. The research was partially supported by M. Rudelson’s NSF Grant DMS-1464514, and USAF Grant FA9550-14-1-0009.
Author information
Authors and Affiliations
Corresponding author
Additional information
Editors in Charge: Günter M. Ziegler and Kenneth Clarkson
Rights and permissions
About this article
Cite this article
Huang, H. John Ellipsoid and the Center of Mass of a Convex Body. Discrete Comput Geom 60, 809–830 (2018). https://doi.org/10.1007/s00454-017-9924-5
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00454-017-9924-5