• Calendar

March 9, Tuesday
12:00 – 14:00

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 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 loglog{1/Epsilon}). Joint Work with Boris Aronov (Polytechnic Institute of NYU),and Micha Sharir (Tel Aviv University).