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 $dn\over 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}$.
Categories: cs.CG cs.DM