Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS

   
Mobile Device Pairing
Green Open Access
Proceedings of the American Mathematical Society
Proceedings of the American Mathematical Society
ISSN 1088-6826(online) ISSN 0002-9939(print)

 

Geometric applications of Chernoff-type estimates and a ZigZag approximation for balls


Authors: S. Artstein-Avidan, O. Friedland and V. Milman
Journal: Proc. Amer. Math. Soc. 134 (2006), 1735-1742
MSC (2000): Primary 46B07; Secondary 60D05, 46B09
Published electronically: December 14, 2005
MathSciNet review: 2204286
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: In this paper we show that the euclidean ball of radius $ 1$ in $ \mathbb{R}^n$ can be approximated up to $ \varepsilon>0$, in the Hausdorff distance, by a set defined by $ N = C(\varepsilon)n$ linear inequalities. We call this set a ZigZag set, and it is defined to be all points in space satisfying $ 50%$ or more of the inequalities. The constant we get is $ C(\varepsilon) = C \ln (1/\varepsilon)/\varepsilon^2$, where $ C$ is some universal constant. This should be compared with the result of Barron and Cheang (2000), who obtained $ N = Cn^2/\varepsilon^2$. The main ingredient in our proof is the use of Chernoff's inequality in a geometric context. After proving the theorem, we describe several other results which can be obtained using similar methods.


References [Enhancements On Off] (What's this?)


Similar Articles

Retrieve articles in Proceedings of the American Mathematical Society with MSC (2000): 46B07, 60D05, 46B09

Retrieve articles in all journals with MSC (2000): 46B07, 60D05, 46B09


Additional Information

S. Artstein-Avidan
Affiliation: Department of Mathematics, Princeton University, Fine Hall, Washington Road, Princeton, New Jersey 08544-1000 – and – School of Mathematics, Institute for Advanced Study, 1 Einstein Drive, Princeton, New Jersey 08540
Email: artstein@princeton.edu

O. Friedland
Affiliation: School of Mathematical Science, Tel Aviv University, Ramat Aviv, Tel Aviv, 69978, Israel
Email: omerfrie@post.tau.ac.il

V. Milman
Affiliation: School of Mathematical Science, Tel Aviv University, Ramat Aviv, Tel Aviv, 69978, Israel
Email: milman@post.tau.ac.il

DOI: http://dx.doi.org/10.1090/S0002-9939-05-08144-X
PII: S 0002-9939(05)08144-X
Received by editor(s): October 26, 2004
Received by editor(s) in revised form: January 18, 2005
Published electronically: December 14, 2005
Additional Notes: This research was partially supported by BSF grant 2002-006 and by FP6 Marie Curie Actions “PHD”
Communicated by: N. Tomczak-Jaegermann
Article copyright: © Copyright 2005 American Mathematical Society