[Colloquium] TTIC Talk: Esther Ezra, Courant NYU

[Julia MacGlashan]

*REMINDER*

When:             *Thursday, May 13 @ 11:00am
*

Where:           * TTIC Conference Room #526*, 6045 S Kenwood Ave, 5th Floor


Who:              * **Esther Ezra*, Courant NYU


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



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

Host:              Tasos Sidiropoulos, tasos at ttic.edu
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20100512/0f28c98c/attachment.htm