Lower bounds for weak epsilon-nets and stair-convexity

Abstract

We derive the first ever superlinear lower bounds for weak epsilon-nets (for fixed dimension $d$). We do this by showing that, if S is a finite grid of points in the plane that is suitably ``stretched' in the y-direction, then every weak 1/r-net for S must have size at least const.r log r.

Our construction readily generalizes to arbitrary dimension: A suitably-stretched grid in R^d yields the lower bound const.r log^(d-1) r.

Keywords

• Lower
• bounds
• epsilon-nets
• stair-convexity