Computational Geometry Seminar

Wednesday, March 28th, 2007, 16:10-18:00

Room 309
Schreiber Building

Weak Epsilon-Nets and Interval Chains

Gabriel Nivasch, Tel Aviv University

Let S be an n-point set in R^d, and let epsilon be a parameter between 0 and 1. A "weak epsilon-net" for S is another set of points N, such that, for every subset S' of S of size at least epsilon*n, the convex hull of S' containts at least one point of N. The problem is to construct weak epsilon-nets that are as small as possible. For convenience, let r = 1/epsilon, so our bounds increase with r.

It is known that every planar set S has a weak 1/r-net of size O(r^2), and every set S in R^d has a weak 1/r-net of size O(r^d * polylog(r)). For certain special cases better bounds are known: If S is planar and in convex position, then S has a weak 1/r-net of size O(r*polylog(r)). And if S is a set of points along the "moment curve" in R^d, then S also has a weak 1/r-net of size O(r*polylog(r)).

In this talk we present improved constructions for the above special cases, achieving almost-linear bounds that involve alpha(r), the inverse Ackermann function. Namely, we show that every planar set S in convex position has a weak 1/r-net of size O(r * alpha(r)). And every point set S along the moment curve in R^d has a weak 1/r-net of size O(r * 2^poly(alpha(r))), where the degree of the polynomial depends on d.

Our constructions result from a reduction to a problem which we call "stabbing interval chains with j-tuples". We derive barely-superlinear upper bounds for this problem, involving functions alpha_i(n) of the inverse Ackermann hierarchy. We also derive almost-matching lower bounds.

Joint work with Noga Alon, Haim Kaplan, Micha Sharir, and Shakhar Smorodinsky.