| AND (2009) | |||||||||||||||
Abstract | |||||||||||||||
| Abstract. 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-nets of size O(rα(r)), where α(r) denotes r the inverse Ackermann function. For point sets along the moment curve in Rd we construct weak 1 r-nets of size r ·2poly(α(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 = (p1,...,pj) is said to stab an interval chain C = I1 ···Ik if each pi 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. ( j) Let z k (n) denote the minimum size of such a family Z. We derive almost-tight upper and lower ( j) | |||||||||||||||
Details der Publikation | |||||||||||||||
| |||||||||||||||