Improved bounds on weak ε-nets for convex sets Chazelle, Bernard Edelsbrunner, Herbert ; https://orcid.org/0000-0002-9823-6833 Grigni, Michelangelo Guibas, Leonidas Sharir, Micha Welzl, Emo 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·2d-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. Springer 1995 info:eu-repo/semantics/article doc-type:article text http://purl.org/coar/resource_type/c_2df8fbb1 https://research-explorer.ista.ac.at/record/4035 Chazelle B, Edelsbrunner H, Grigni M, Guibas L, Sharir M, Welzl E. Improved bounds on weak ε-nets for convex sets. <i>Discrete &#38; Computational Geometry</i>. 1995;13(1):1-15. doi:<a href="https://doi.org/10.1007/BF02574025">10.1007/BF02574025</a> eng info:eu-repo/semantics/altIdentifier/doi/10.1007/BF02574025 info:eu-repo/semantics/altIdentifier/issn/0179-5376 info:eu-repo/semantics/closedAccess