  According to a well known theorem of Haussler and Welzl (1987), any range
space of bounded VC-dimension admits an $\eps$-net of size
$O\left(\frac{1}{\eps}\log\frac1{\eps}\right)$. Using probabilistic techniques,
Pach and Woeginger (1990) showed that there exist range spaces of VC-dimension
2, for which the above bound can be attained. The only known range spaces of
small VC-dimension, in which the ranges are geometric objects in some Euclidean
space and the size of the smallest $\eps$-nets is superlinear in
$\frac1{\eps}$, were found by Alon (2010). In his examples, the size of the
smallest $\eps$-nets is $\Omega\left(\frac{1}{\eps}g(\frac{1}{\eps})\right)$,
where $g$ is an extremely slowly growing function, closely related to the
inverse Ackermann function.
  \smallskip
  We show that there exist geometrically defined range spaces, already of
VC-dimension $2$, in which the size of the smallest $\eps$-nets is
$\Omega\left(\frac{1}{\eps}\log\frac{1}{\eps}\right)$. We also construct range
spaces induced by axis-parallel rectangles in the plane, in which the size of
the smallest $\eps$-nets is
$\Omega\left(\frac{1}{\eps}\log\log\frac{1}{\eps}\right)$. By a theorem of
Aronov, Ezra, and Sharir (2010), this bound is tight.
