Title:  Small-Size Epsilon-Nets for Geometric Range Spaces 

Speaker: Esther Ezra, NYU 

Abstract: 


Since their introduction in 1987 by Haussler and Welzl, Epsilon-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), and a parameter 0 < Epsilon < 1, an Epsilon-net for (X,R) is a subset N of X with
the property that any range that captures at least an Epsilon-fraction of X 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 Epsilon-nets. Specifically,
the Epsilon-Net Theorem of Haussler and Welzl asserts that in this case there exists an Epsilon-net of size O(1/Epsilon \log{1/Epsilon}).
One of the major questions in the theory of Epsilon-nets, open since their introduction more than 20 years ago, is whether the factor
\log{1/Epsilon} 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 Epsilon-net of size O((1/Epsilon) f(1/Epsilon)), 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 Epsilon-nets. I will then discuss range spaces of points and
axis-parallel boxes in two and three dimensions, and show that they admit an Epsilon-net of size O(1/Epsilon \log\log{1/Epsilon}).

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