Abstract: Epsilon nets are among the most important constructs
in computational and combinatorial geometry (and in learning theory too).
Given a set X of n objects, a collection of subsets (`ranges') R, and
a parameter eps > 0, the goal is to show the existence of
a small subset N of X, so that any range r in R which contains at least
eps*n points of X must intersect N.

The classical 1987 theorem of Haussler and Welzl shows the existence of
eps-nets of size O((1/eps) log(1/eps)), if (X,R) has so-called finite
VC-dimension. The goal is to improve this further, ideally to
O(1/eps) --- the only known lower bound in geometric contexts is Omega(1/eps).
Some such improvements have been obtained, as early as 1990, with many more
discovered very recently.

In this talk we present an improved upper bound of O(r\log\log r) for
the size of (1/r)-nets for points and axis-parallel rectangles in the plane
(or boxes in 3-space). The new paradigm can also be extended to other instances,
such as points and fat triangles in the plane.

(Joint work with Esther Ezra and Boris Aronov.)

We have also re-examined the old results on the existence of eps-nets of
size O(1/eps) for halfspaces in two and three dimensions, and have come up
with *many* new and simple proofs.
This is still work in progress and we are trying to apply the new proofs to
several new instances as well.

(Joint work with Esther Ezra, Sariel Har-Peled, Haim Kaplan, and
Shakhar Smorodinsky.)