Small Strong Epsilon Nets

Abstract

Let P be a set of n points in ${\mathbb{R}}^d$. A point x is said to be a centerpoint of P if x is contained in every convex object that contains more than $\frac{dn}{d+1}$ points of P. We call a point x a strong centerpoint for a family of objects $\mathcal{C}$ if $x\in P$ is contained in every object $C\in \mathcal{C}$ that contains more than a constant fraction of points of P. A strong centerpoint does not exist even for halfspaces in ${\mathbb{R}}^2$. We prove that a strong centerpoint exists for axis-parallel boxes in ${\mathbb{R}}^d$ and give exact bounds. We then extend this to small strong $\epsilon$-nets in the plane and prove upper and lower bounds for ${\epsilon }_i^{\mathcal{S}}$ where $\mathcal{S}$ is the family of axis-parallel rectangles, halfspaces and disks. Here ${\epsilon }_i^{\mathcal{S}}$ represents the smallest real number in $[0,1]$ such that there exists an ${\epsilon }_i^{\mathcal{S}}$-net of size i with respect to $\mathcal{S}$.

19 pages, 12 figures