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

Original language | English (US) |
---|---|

Title of host publication | Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms |

Pages | 1194-1203 |

Number of pages | 10 |

State | Published - Dec 1 2008 |

Externally published | Yes |

Event | 19th Annual ACM-SIAM Symposium on Discrete Algorithms - San Francisco, CA, United States Duration: Jan 20 2008 → Jan 22 2008 |

### Publication series

Name | Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms |
---|

### Other

Other | 19th Annual ACM-SIAM Symposium on Discrete Algorithms |
---|---|

Country | United States |

City | San Francisco, CA |

Period | 1/20/08 → 1/22/08 |

### All Science Journal Classification (ASJC) codes

- Software
- Mathematics(all)

## Fingerprint Dive into the research topics of 'Weak ∈-nets and interval chains'. Together they form a unique fingerprint.

## Cite this

*Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms*(pp. 1194-1203). (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms).