Improved bounds on weak ε-nets for convex sets
From MaRDI portal
Publication:5248519
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
Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items
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
