Improved bounds on weak ε-nets for convex sets

DOI10.1145/167088.167222zbMath1310.68201OpenAlexW2008531343MaRDI QIDQ5248519

Micha Sharir, Michelangelo Grigni, Bernard Chazelle, Leonidas J. Guibas, Ermo Welzl, Herbert Edelsbrunner

Publication date: 7 May 2015

Published in: Proceedings of the twenty-fifth annual ACM symposium on Theory of computing - STOC '93 (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/167088.167222

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (10)

Almost optimal set covers in finite VC-dimension ⋮ An optimal generalization of the colorful Carathéodory theorem ⋮ An optimal extension of the centerpoint theorem ⋮ Core-Sets: Updated Survey ⋮ Discrete Voronoi games and \(\epsilon\)-nets, in two and three dimensions ⋮ Weak \(\varepsilon \)-nets have basis of size \(O(1/\varepsilon\log (1/\varepsilon))\) in any dimension ⋮ Reprint of: Weak \(\varepsilon\)-nets have basis of size \(O(1/{\epsilon}\log (1/\epsilon))\) in any dimension ⋮ Radon numbers and the fractional Helly theorem ⋮ Unnamed Item ⋮ The discrete yet ubiquitous theorems of Carathéodory, Helly, Sperner, Tucker, and Tverberg

This page was built for publication: Improved bounds on weak ε-nets for convex sets