Lower bounds for weak epsilon-nets and stair-convexity (Q532609)

Let \(X\) be a finite set in the \(d\)-dimensional space. A set \(N\) in the \(d\)-dimensional space is called a weak \(\varepsilon\)-net for \(X\) (where \(\varepsilon \in (0,1]\)), if \(N\) intersects every convex set \(C\) with \(|X \cap C | \geq \varepsilon |X|\). The main result of this paper is a superlinear lower bound for every fixed dimension \(d\). The authors are able to construct, for every fixed \(d \geq 2\) and every \(r \geq 1\), sets \(X\) in the \(d\)-dimensional space for which every weak \(\frac{1}{r}\)-net has at least \(\Omega(r \log^{d-1} r)\) points. For this result the authors use a stretched grid (the Cartesian product of \(d\) suitable fast-growing finite sequences). To look at convexity on these grids they use stair-convexity (a new variant of the usual notion of convexity). By considering weak \(\varepsilon\)-nets for the diagonal of the above mentioned stretched grid, the authors can show that the upper bounds by \textit{N. Alon} et al. [``Weak \(\varepsilon\)-nets and interval chains'', J. ACM 55, No.~6, article 28 (2008), \url{doi:10.1145/1455248.1455252}] are quite good in the worst case. However, still the general gaps between lower and upper bounds for \(\varepsilon\)-nets are quite large. The authors conjecture that no sets in general position in the \(d\)-dimensional space (with \(r \geq 3\)) admit linear-size weak \(\frac{1}{r}\)-nets.