## Abstract

Let S be a set of n points in ℝ^{ d} . A set W is a weak ε-net for (convex ranges of)S if, for any T⊆S containing εn points, the convex hull of T intersects W. We show the existence of weak ε-nets of size {Mathematical expression}, where β_{ 2}=0, β_{ 3}=1, and β_{ d} ≈0.149·2^{ d-1}(d-1)!, improving a previous bound of Alon et al. Such a net can be computed effectively. We also consider two special cases: when S is a planar point set in convex position, we prove the existence of a net of size O((1/ε) log^{1.6}(1/ε)). In the case where S consists of the vertices of a regular polygon, we use an argument from hyperbolic geometry to exhibit an optimal net of size O(1/ε), which improves a previous bound of Capoyleas.

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

Pages (from-to) | 1-15 |

Number of pages | 15 |

Journal | Discrete & Computational Geometry |

Volume | 13 |

Issue number | 1 |

DOIs | |

State | Published - Dec 1995 |

## All Science Journal Classification (ASJC) codes

- Theoretical Computer Science
- Geometry and Topology
- Discrete Mathematics and Combinatorics
- Computational Theory and Mathematics