Random approximation and the vertex index of convex bodies

详细信息    查看全文

• 作者：Silouanos Brazitikos ; Giorgos Chasapis ; Labrini Hioni
• 关键词：Convex bodies ; Isotropic position ; Centroid bodies ; Random polytopal approximation
• 刊名：Archiv der Mathematik
• 出版年：2017
• 出版时间：February 2017
• 年：2017
• 卷：108
• 期：2
• 页码：209-221
• 全文大小：
• 刊物类别：Mathematics and Statistics
• 刊物主题：Mathematics, general;
• 出版者：Springer International Publishing
• ISSN：1420-8938
• 卷排序：108

文摘

We prove that there exists an absolute constant \({\alpha > 1}\) with the following property: if K is a convex body in \({{\mathbb R}^n}\) whose center of mass is at the origin, then a random subset \({X\subset K}\) of cardinality \({{\rm card}(X)=\lceil\alphan\rceil }\) satisfies with probability greater than \({1-e^{-c_1n}}\)$$K\subseteq c_2n\, {\rm conv}(X),$$where \({c_1, c_2 > 0}\) are absolute constants. As an application we show that the vertex index of any convex body K in \({{\mathbb R}^n}\) is bounded by \({c_3n^2}\), where \({c_3 > 0}\) is an absolute constant, thus extending an estimate of Bezdek and Litvak for the symmetric case.KeywordsConvex bodiesIsotropic positionCentroid bodiesRandom polytopal approximationMathematics Subject ClassificationPrimary 52A23Secondary 52A3546B0660D05References1.S. Artstein-Avidan, A. Giannopoulos, and V. D. Milman, Asymptotic Geometric Analysis, Part I, Mathematical Surveys and Monographs 202, Amer. Math. Soc., Providence, RI, 2015.2.Ball K. M., Pajor A.: Convex bodies with few faces. Proc. Amer. Math. Soc. 110, 225–231 (1990)MathSciNetCrossRefMATHGoogle Scholar3.A. Barvinok, Thrifty approximations of convex bodies by polytopes, Int. Math. Res. Not. IMRN (2014), 4341–4356.4.J. Batson, D. Spielman, and N. Srivastava, Twice-Ramanujan Sparsifiers, STOC’ 2009: Proceedings of the 41st annual ACM Symposium on Theory of Computing, ACM, New York, 2009, pp. 255–262.5.Bezdek K.: The illumination conjecture and its extensions. Period. Math. Hungar. 53, 59–69 (2006)MathSciNetCrossRefMATHGoogle Scholar6.Bezdek K., Litvak A.E.: On the vertex index of convex bodies. Adv. Math. 215, 626–641 (2007)MathSciNetCrossRefMATHGoogle Scholar7.J. Bourgain, On the distribution of polynomials on high dimensional convex sets, in Geom. Aspects of Funct. Analysis, Lecture Notes in Mathematics 1469, Springer, Berlin, 1991, 127–137.8.S. Brazitikos, Quantitative Helly-type theorem for the diameter of convex sets, Preprint (arXiv:1511.07779).9.S. Brazitikos, A. Giannopoulos, P. Valettas, and B-H. Vritsiou, Geometry of isotropic convex bodies, Mathematical Surveys and Monographs 196, American Mathematical Society, Providence, RI, 2014.10.Dafnis N., Giannopoulos A., Tsolomitis A.: Asymptotic shape of a random polytope in a convex body. J. Funct. Anal. 257, 2820–2839 (2009)MathSciNetCrossRefMATHGoogle Scholar11.Giannopoulos A., Milman V. D.: Concentration property on probability spaces. Adv. Math. 156, 77–106 (2000)MathSciNetCrossRefMATHGoogle Scholar12.Gluskin E. D., Litvak A. E.: Asymmetry of convex polytopes and vertex index of symmetric convex bodies. Discrete Comput. Geom. 40, 528–536 (2008)MathSciNetCrossRefMATHGoogle Scholar13.E. D. Gluskin and A. E. Litvak, A remark on vertex index of the convex bodies, in Geom. Aspects of Funct. Analysis, Lecture Notes in Math. 2050, Springer, Berlin, 2012, 255–265.14.Guédon O., Milman E.: Interpolating thin-shell and sharp large-deviation estimates for isotropic log-concave measures. Geom. Funct. Anal. 21, 1043–1068 (2011)MathSciNetCrossRefMATHGoogle Scholar15.Haberl C.: \({L_p}\) intersection bodies. Adv. Math. 217, 2599–2624 (2008)MathSciNetCrossRefMATHGoogle Scholar16.F. John, Studies and Essays Presented to R. Courant on his 60th Birthday, January 8, 1948, 187–204. Interscience Publishers, Inc., New York, N. Y., 1948.17.Kannan R., Lovász L., Simonovits M.: Isoperimetric problems for convex bodies and a localization lemma. Discrete Comput. Geom. 13, 541–559 (1995)MathSciNetCrossRefMATHGoogle Scholar18.Klartag B.: On convex perturbations with a bounded isotropic constant. Geom. Funct. Anal. 16, 1274–1290 (2006)MathSciNetCrossRefMATHGoogle Scholar19.Klartag B., Milman E.: Centroid bodies and the logarithmic Laplace transform—a unified approach, J. Funct. Anal. 262 (2012), 10–34.MathSciNetCrossRefMATHGoogle Scholar20.Lutwak E., Yang D., Zhang G.: \({L^p}\) affine isoperimetric inequalities. J. Differential Geom. 56, 111–132 (2000)MathSciNetMATHGoogle Scholar21.V. D. Milman and A. Pajor, Isotropic position and inertia ellipsoids and zonoids of the unit ball of a normed n-dimensional space, in Geom. Aspects of Funct. Analysis, Lecture Notes in Mathematics 1376, Springer, Berlin, 1989, 64–104.22.Paouris G.: Concentration of mass in convex bodies. Geom. Funct. Anal. 16, 1021–1049 (2006)MathSciNetCrossRefMATHGoogle Scholar23.Paouris G.: Small ball probability estimates for log-concave measures. Trans. Amer. Math. Soc. 364, 287–308 (2012)MathSciNetCrossRefMATHGoogle Scholar24.Paouris G., Werner E.: Relative entropy of cone measures and \({L_p}\)-centroid bodies. Proc. Lond. Math. Soc. 104, 253–286 (2012)MathSciNetCrossRefMATHGoogle Scholar25.R. Schneider, Convex Bodies: The Brunn-Minkowski Theory, Second expanded edition. Encyclopedia of Mathematics and Its Applications 151, Cambridge University Press, Cambridge, 2014.26.N. Srivastava, On contact points of convex bodies, in Geom. Aspects of Funct. Analysis, Lecture Notes in Mathematics 2050, Springer, Berlin, 2012, 393–412.Copyright information© Springer International Publishing 2016Authors and AffiliationsSilouanos Brazitikos1Giorgos Chasapis1Email authorLabrini Hioni11.Department of MathematicsNational and Kapodistrian University of AthensAthensGreece About this article CrossMark Publisher Name Springer International Publishing Print ISSN 0003-889X Online ISSN 1420-8938 About this journal Reprints and Permissions Article actions .buybox { margin: 16px 0 0; position: relative; } .buybox { font-family: Source Sans Pro, Helvetica, Arial, sans-serif; font-size: 14px; font-size: .875rem; } .buybox { zoom: 1; } .buybox:after, .buybox:before { content: ''; display: table; } .buybox:after { clear: both; } /*---------------------------------*/ .buybox .buybox__header { border: 1px solid #b3b3b3; border-bottom: 0; padding: 8px 12px; position: relative; background-color: #f2f2f2; } .buybox__header .buybox__login { font-family: Source Sans Pro, Helvetica, Arial, sans-serif; font-size: 14px; font-size: .875rem; letter-spacing: .017em; display: inline-block; line-height: 1.2; padding: 0; } .buybox__header .buybox__login:before { position: absolute; top: 50%; -webkit-transform: perspective(1px) translateY(-50%); transform: perspective(1px) translateY(-50%); content: '\A'; width: 34px; height: 34px; left: 10px; } /*---------------------------------*/ .buybox .buybox__body { padding: 0; padding-bottom: 16px; position: relative; text-align: center; background-color: #fcfcfc; border: 1px solid #b3b3b3; } .buybox__body .buybox__section { padding: 16px 12px 0 12px; text-align: left; } .buybox__section .buybox__buttons { text-align: center; width: 100%; } /********** mycopy buybox specific **********/ .buybox.mycopy__buybox .buybox__section .buybox__buttons { border-top: 0; padding-top: 0; } /******/ .buybox__section:nth-child(2) .buybox__buttons { border-top: 1px solid #b3b3b3; padding-top: 20px; } .buybox__buttons .buybox__buy-button { display: inline-block; text-align: center; margin-bottom: 5px; padding: 6px 12px; } .buybox__buttons .buybox__price { white-space: nowrap; text-align: center; font-size: larger; padding-top: 6px; } .buybox__section .buybox__meta { letter-spacing: 0; padding-top: 12px; } .buybox__section .buybox__meta:only-of-type { padding-top: 0; position: relative; bottom: 6px; } /********** mycopy buybox specific **********/ .buybox.mycopy__buybox .buybox__section .buybox__meta { margin-top: 0; margin-bottom: 0; } /******/ .buybox__meta .buybox__product-title { display: inline; font-weight: bold; } .buybox__meta .buybox__list { line-height: 1.3; } .buybox__meta .buybox__list li { position: relative; padding-left: 1em; list-style: none; margin-bottom: 5px; } .buybox__meta .buybox__list li:before { font-size: 1em; content: '\2022'; float: left; position: relative; top: .1em; font-family: serif; font-weight: 600; text-align: center; line-height: inherit; color: #666; width: auto; margin-left: -1em; } .buybox__meta .buybox__list li:last-child { margin-bottom: 0; } /*---------------------------------*/ .buybox .buybox__footer { border: 1px solid #b3b3b3; border-top: 0; padding: 8px 12px; position: relative; border-style: dashed; } /*-----------------------------------------------------------------*/ @media screen and (min-width: 460px) and (max-width: 1074px) { .buybox__body .buybox__section { display: inline-block; vertical-align: top; padding: 12px 12px; padding-bottom: 0; text-align: left; width: 48%; } .buybox__body .buybox__section { padding-top: 16px; padding-left: 0; } .buybox__section:nth-of-type(2) .buybox__meta { border-left: 1px solid #d3d3d3; padding-left: 28px; } .buybox__section:nth-of-type(2) .buybox__buttons { border-top: 0; padding-top: 0; padding-left: 16px ; } .buybox__buttons .buybox__buy-button { } /********** article buybox specific **********/ .buybox.article__buybox .buybox__section:nth-of-type(2) { margin-top: 16px; padding-top: 0; } .buybox.article__buybox .buybox__section:nth-of-type(2) .buybox__meta { margin-top: 40px; padding-top: 0; padding-bottom: 45px; } .buybox.article__buybox .buybox__section:nth-of-type(2) .buybox__meta:only-of-type { margin-top: 8px; padding-top: 12px; padding-bottom: 12px; } /********** mycopy buybox specific **********/ .buybox.mycopy__buybox .buybox__section:first-child { width: 69%; } .buybox.mycopy__buybox .buybox__section:last-child { width: 29%; } /******/ } /*-----------------------------------------------------------------*/ @media screen and (max-width: 459px) { /********** mycopy buybox specific **********/ .buybox.mycopy__buybox .buybox__body { padding-bottom: 5px; } .buybox.mycopy__buybox .buybox__section:last-child { text-align: center; width: 100%; } .buybox.mycopy__buybox .buybox__buttons { display: inline-block; width: 150px ; } /******/ } /*-----------------------------------------------------------------*/ Log in to check access Buy (PDF) EUR 34,95 Unlimited access to the full article Instant download Include local sales tax if applicable Find out about institutional subscriptions (function () { var forEach = function (array, callback, scope) { for (var i = 0; i Export citation .RIS Papers Reference Manager RefWorks Zotero .ENW EndNote .BIB BibTeX JabRef Mendeley Share article Email Facebook Twitter LinkedIn Cookies We use cookies to improve your experience with our site. More information Accept Over 10 million scientific documents at your fingertips