Computer Science Colloquium, 2008-2009

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).