TY - GEN

T1 - Weak ∈-nets and interval chains

AU - Alon, Noga

AU - Kaplan, Haim

AU - Nivasch, Gabriel

AU - Sharir, Micha

AU - Smorodinsky, Shakhar

PY - 2008/12/1

Y1 - 2008/12/1

N2 - We construct weak ∈-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 0(r α(r)), where α(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(α(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 = [l,n], an interval chain of length k is a sequence of k consecutive, disjoint, nonempty intervals contained in N. A jtuple p̄ = (p i,..., 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 double-struck Z of j-tuples that stabs all k-interval chains in N. Let z (j) k (n) denote the minimum size of such a family double-struck Z. We derive almost-tight upper and lower bounds for z (j) k (n) for every fixed j; our bounds involve functions α m(n) of the inverse Ackermann hierarchy. Specifically, we show that for j - 3 we have z (3) k (n) = Θ(nα[k/2] (n)) for all k ≥ 6. For each j ≥ 4 we construct a pair of functions P 1 j(m), Q 1 j(m), almost equal asymptotically, such that z (j) P′j(m)(n) = 0(nα m(n)) and z (j) Q'j(m)(n) = Ω(nα m(n)).

AB - We construct weak ∈-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 0(r α(r)), where α(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(α(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 = [l,n], an interval chain of length k is a sequence of k consecutive, disjoint, nonempty intervals contained in N. A jtuple p̄ = (p i,..., 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 double-struck Z of j-tuples that stabs all k-interval chains in N. Let z (j) k (n) denote the minimum size of such a family double-struck Z. We derive almost-tight upper and lower bounds for z (j) k (n) for every fixed j; our bounds involve functions α m(n) of the inverse Ackermann hierarchy. Specifically, we show that for j - 3 we have z (3) k (n) = Θ(nα[k/2] (n)) for all k ≥ 6. For each j ≥ 4 we construct a pair of functions P 1 j(m), Q 1 j(m), almost equal asymptotically, such that z (j) P′j(m)(n) = 0(nα m(n)) and z (j) Q'j(m)(n) = Ω(nα m(n)).

UR - http://www.scopus.com/inward/record.url?scp=58449088193&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=58449088193&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:58449088193

SN - 9780898716474

T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

SP - 1194

EP - 1203

BT - Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms

T2 - 19th Annual ACM-SIAM Symposium on Discrete Algorithms

Y2 - 20 January 2008 through 22 January 2008

ER -