Name
Abstract | ||
|---|---|---|
We construct weak epsilon-nets of almost linear size for certain types of point sets. Specifically, for planar point sets in convex position we construct weak 1/r-nets of size O(r alpha(r)), where alpha(r) denotes the inverse Ackermann function. For point sets along the moment curve in R(d) we construct weak 1/r-nets of size r . 2(poly(alpha(r))), where the degree of the polynomial in the exponent depends (quadratically) on d. Our constructions result from a reduction to a new problem, which we call stabbing interval chains with j-tuples. Given the range of integers N = [1, n], an interval chain of length k is a sequence of k consecutive, disjoint, nonempty intervals contained in N. A j-tuple (p) over bar = (p(1),..., p(j)) is said to stab an interval chain C = I(1) ... I(k) if each p(i) falls on a different interval of C. The problem is to construct a small-size family Z of j-tuples that stabs all k-interval chains in N. Let z(k)((j)) (n) denote the minimum size of such a family Z. We derive almost-tight upper and lower bounds for z(k)((j)) (n) for every fixed j; our bounds involve functions am(n) of the inverse Ackermann hierarchy. Specifically, we show that for j = 3 we have z(k)((3)) (n) = Theta (n alpha([k/2]) (n)) for all k >= 6. For each j >= 4, we construct a pair of functions P'(j) (m), Q'(j) (m), almost equal asymptotically, such that z(P'j(m))((j)) (n) - O(n alpha(m)(n)) and z(Q'j(m))((j)) (n) = Omega(n alpha(m)(n)). |
Year | DOI | Venue |
|---|---|---|
2008 | 10.1145/1455248.1455252 | JOURNAL OF THE ACM |
Keywords | DocType | Volume |
Interval chain,inverse Ackermann function,moment curve,weak epsilon-net | Journal | 55 |
Issue | ISSN | Citations |
6 | 0004-5411 | 5 |
PageRank | References | Authors |
0.44 | 6 | 5 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Noga Alon | 1 | 10468 | 1688.16 |
| Haim Kaplan | 2 | 3581 | 263.96 |
| Gabriel Nivasch | 3 | 72 | 10.20 |
| Micha Sharir | 4 | 8405 | 1183.84 |
| Shakhar Smorodinsky | 5 | 422 | 43.47 |