A lower bound for weak \(\varepsilon\)-nets in high dimension (Q1611071): Difference between revisions

A finite set \(N\subset \mathbb{R}^{d}\) is called a weak \(\varepsilon \)-net for an \(n\)-point set \(X\subset \mathbb{R}^{d}\) if it intersects each convex set \(K\) with \(\left|K\cap X\right|\geq \varepsilon n\). It is shown that there are point sets in \(\mathbb{R}^{d}\) for which every weak \(\frac{1}{50}\)-net has at least \(const\cdot e^{\sqrt{d/2}}\) points. The best available upper bound for the size of a weak \(\varepsilon \)-net with fixed \(\varepsilon >0\) is \(d^{O(d)}\).