Abstract:

Since their introduction in 1987 by Haussler and Welzl, 
\eps-nets have become one of the central concepts in 
computational and combinatorial geometry, and have been
used in a variety of applications, such as range searching,
geometric partitions, and bounds on curve-point incidences.
In particular, they are strongly related to geometric set-cover
and hitting-set problems.

A range space (or a hypergraph) (X,R) is a pair consisting of 
an underlying universe X of objects, and a certain collection 
R of subsets of X (also called ranges).
Given a range space (X,R), a finite subset P of X, and a
parameter 0 < \eps < 1, an \eps-net for P and R is a subset 
N of P with the property that any range that captures at least 
\eps-fraction of the points of P contains an element of N. 
In other words, N is a hitting set for all the ``heavy'' ranges.

Of particular interest are geometric range spaces, since then they
admit small-size \eps-nets.
Specifically, the Epsilon-Net Theorem of Haussler and Welzl asserts that
in this case there exists an \eps-net of size O(1/\eps \log{1/\eps}). 
One of the major questions in the theory of \eps-nets, open since
their introduction more than 20 years ago, is whether the factor
\log{1/\eps} in the upper bound on their size is really necessary, 
especially in typical low-dimensional geometric situations.
A central motivation then arises from the technique of Bronnimann and
Goodrich to obtain, in polynomial time, improved approximation factors for
the geometric hitting-set and set-cover problems: The existence of an \eps-net 
of size O((1/\eps) f(1/\eps)), for some slowly-growing function f(.), 
implies an approximation factor of O(f(OPT)), where OPT is the size of the 
smallest such set.

In this talk I will survey some of the fundamental results concerning
small-size \eps-nets. I will then discuss range spaces of points and 
axis-parallel boxes in two and three dimensions, and show that they admit 
an \eps-net of size O(1/\eps \log\log{1/\eps}), and also present several
extensions to "fat" planar ranges. 

Joint work with Boris Aronov (Polytechnic Institute of NYU) and Micha Sharir
(Tel Aviv University).