Strong Lower Bounds for Weak Epsilon-Nets

Abstract

Let $P$ be a finite point set in ${\mathbb{R}}^d$. A weak $\epsilon$-net for $P$ with respect to convex sets is a finite set $X\subset {\mathbb{R}}^d$ intersecting every convex set containing at least $\epsilon |P|$ points of $P$. Determining their optimal worst-case size was described by Alon, Kalai, Matousek, and Meshulam [Adv. Appl. Math., 2002] as "one of the truly important open problems in combinatorial geometry." We give elementary constructions which establish the first polynomially superlinear lower bounds in fixed dimension. Already in ${\mathbb{R}}^3$, we construct point sets for which every weak $\epsilon$-net has size $\Omega ({\epsilon }^{-3/2})$. More generally, for every fixed $d\ge 3$, we obtain a lower bound of ${\Omega }_d({\epsilon }^{-{\gamma }_d})$, where ${\gamma }_d=\sqrt{d/2}+O(1)$. Consequently, no upper bound of the form $O_d({\epsilon }^{-C})$ can hold with an absolute constant $C$ which is independent of the dimension. Despite the recent progress on upper bounds, the strongest previous general lower bound remained ${\Omega }_d({\epsilon }^{-1}{\log }^{d-1}(1/\epsilon ))$, due to Bukh, Matousek, and Nivasch [Israel J. Math., 2011]. To obtain our results, we apply a quadratic lift to grid-based configurations with many point-line incidences. The bounds also yield polynomial separations between fractional and integral piercing numbers of convex families, and lower bounds for Hadwiger-Debrunner numbers.