Saurabh Ray
ABSTRACT
Given a set P of n points in Rd and ε > 0, we consider the problemof constructing weak ε-nets for P.We show the following: pick a random sample Q of size O(1/ε log (1/ε)) from P. Then, with constant probability, a weak ε-net of P can be constructed from only the points of Q. This shows that weak ε-nets in Rd can be computed from a subset of P of size O(1/ε log(1/ε)) with only the constant of proportionality depending on the dimension, unlike all previous work where the size of the subset had the dimension in the exponent of 1/ε. However, our final weak ε-nets still have a large size (with the dimension appearing in the exponent of 1/ε).
- N. Alon and D. Kleitman. Piercing convex sets and the hadwiger debrunner (p; q)-problem. Adv. Math., 96(1):103--112, 1992.Google Scholar
Cross Ref
- Noga Alon, Imre Bárány, Zoltán Füredi, and Daniel J. Kleitman. Point selections and weak ε--nets for convex hulls. Combinatorics, Probability & Computing, 1:189--200, 1992.Google ScholarCross Ref
- Bernard Chazelle, Herbert Edelsbrunner, Michelangelo Grigni, Leonidas Guibas, Micha Sharir, and Emo Welzl. Improved bounds on weak ε-nets for convex sets. In STOC '93: Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, pages 495--504, 1993. Google ScholarDigital Library
- Reinhard Diestel. Graph theory. Springer-Verlag, New York, 2000.Google Scholar
- D. Haussler and E. Welzl. ε-nets and simplex range queries. Discrete Comput. Geom., 2:127--151, 1987.Google ScholarDigital Library
- Jirí Matousek. Lectures in Discrete Geometry. Springer-Verlag, New York, NY, 2002. Google ScholarDigital Library
- Jirí Matousek and Uli Wagner. New constructions of weak ε-nets. Discrete & Computational Geometry, 32(2):195--206, 2004. Google ScholarDigital Library
- Edgar A. Ramos. Equipartition of mass distributions by hyperplanes. Discrete & Computational Geometry, 15(2):147--167, 1996.Google ScholarDigital Library
Index Terms
- Weak ε-nets have basis of size o(1/ε log (1/ε)) in any dimension
Recommendations
Weak ε-nets have basis of size O (1/εlog(1/ε)) in any dimension
Given a set P of n points in R^d and @e>0, we consider the problem of constructing weak @e-nets for P. We show the following: pick a random sample Q of size O(1/@elog(1/@e)) from P. Then, with constant probability, a weak @e-net of P can be constructed ...
Convex hulls of spheres and convex hulls of disjoint convex polytopes
Given a set @S of spheres in E^d, with d>=3 and d odd, having a constant number of m distinct radii @r"1,@r"2,...,@r"m, we show that the worst-case combinatorial complexity of the convex hull of @S is @Q(@__ __"1"=<"i"<>"j"=<"mn"in"j^@__ __^d^2^@__ __), ...
Lower bounds for weak epsilon-nets and stair-convexity
SCG '09: Proceedings of the twenty-fifth annual symposium on Computational geometryA set N ⊂ Rd is called a weak ε-net (with respect to convex sets) for a finite X ⊂ Rd if N intersects every convex set C with |X ∩ C|≥ε|X|. For every fixed d≥ 2 and every r≥ 1 we construct sets X⊂ Rd for which every weak 1/r-net has at least Ω(r logd-1 ...
Comments