Lower bounds for weak epsilon-nets and stair-convexity
Boris Bukh, Jiřı́ Matoušek, Gabriel Nivasch · 2009
A set N ⊂ Rd is called a weak ε-net (with respect to convex sets) for a finite X ⊂ Rd if N intersects every convex set C with |X ∩ C|≥ε|X|. For every fixed d≥ 2 and every r≥ 1 we construct sets X⊂ Rd for which every weak 1/r-net has at least Ω(r logd-1 r) points; this is the first superlinear lower bound for weak ε-nets in a fixed dimension.