Improved bounds on weak ε-nets for convex sets

B. Chazelle, H. Edelsbrunner, M. Grigni, L. Guibas, M. Sharir, E. Welzl, Discrete & Computational Geometry 13 (1995) 1–15.

Download
No fulltext has been uploaded. References only!

Journal Article | Published
Author
; ; ; ; ;
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·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.
Publishing Year
Date Published
1995-12-01
Journal Title
Discrete & Computational Geometry
Volume
13
Issue
1
Page
1 - 15
IST-REx-ID

Cite this

Chazelle B, Edelsbrunner H, Grigni M, Guibas L, Sharir M, Welzl E. Improved bounds on weak ε-nets for convex sets. Discrete & Computational Geometry. 1995;13(1):1-15. doi:10.1007/BF02574025
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
Chazelle, Bernard, Herbert Edelsbrunner, Michelangelo Grigni, Leonidas Guibas, Micha Sharir, and Emo Welzl. “Improved Bounds on Weak ε-Nets for Convex Sets.” Discrete & Computational Geometry 13, no. 1 (1995): 1–15. https://doi.org/10.1007/BF02574025.
B. Chazelle, H. Edelsbrunner, M. Grigni, L. Guibas, M. Sharir, and E. Welzl, “Improved bounds on weak ε-nets for convex sets,” Discrete & Computational Geometry, vol. 13, no. 1, pp. 1–15, 1995.
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.
Chazelle, Bernard, et al. “Improved Bounds on Weak ε-Nets for Convex Sets.” Discrete & Computational Geometry, vol. 13, no. 1, Springer, 1995, pp. 1–15, doi:10.1007/BF02574025.

Export

Marked Publications

Open Data IST Research Explorer

Search this title in

Google Scholar