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

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.