Improved bounds on weak ε-nets for convex sets

B. Chazelle, H. Edelsbrunner, M. Grigni, L. Guibas, M. Sharir, E. Welzl

Research output: Contribution to journalArticle

33 Scopus citations

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/ε) log1.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 languageEnglish (US)
Pages (from-to)1-15
Number of pages15
JournalDiscrete & Computational Geometry
Volume13
Issue number1
DOIs
StatePublished - Dec 1 1995

All Science Journal Classification (ASJC) codes

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

Fingerprint Dive into the research topics of 'Improved bounds on weak ε-nets for convex sets'. Together they form a unique fingerprint.

  • Cite this

    Chazelle, B., Edelsbrunner, H., Grigni, M., Guibas, L., Sharir, M., & Welzl, E. (1995). Improved bounds on weak ε-nets for convex sets. Discrete & Computational Geometry, 13(1), 1-15. https://doi.org/10.1007/BF02574025