Matoušek, Jiří; Wagner, UliIST Austria
A finite set N ⊃ Rd is a weak ε-net for an n-point set X ⊃ Rd (with respect to convex sets) if N intersects every convex set K with |K ∩ X| ≥ εn. We give an alternative, and arguably simpler, proof of the fact, first shown by Chazelle et al. , that every point set X in Rd admits a weak ε-net of cardinality O(ε-d polylog(1/ε)). Moreover, for a number of special point sets (e.g., for points on the moment curve), our method gives substantially better bounds. The construction yields an algorithm to construct such weak ε-nets in time O(n ln(1/ε)). We also prove, by a different method, a near-linear upper bound for points uniformly distributed on the (d - 1)-dimensional sphere.
129 - 135
SoCG: Symposium on Computational Geometry
Matoušek J, Wagner U. New constructions of weak epsilon-nets. In: ACM; 2003:129-135. doi:10.1145/777792.777813
Matoušek, J., & Wagner, U. (2003). New constructions of weak epsilon-nets (pp. 129–135). Presented at the SoCG: Symposium on Computational Geometry, ACM. https://doi.org/10.1145/777792.777813
Matoušek, Jiří, and Uli Wagner. “New Constructions of Weak Epsilon-Nets,” 129–35. ACM, 2003. https://doi.org/10.1145/777792.777813.
J. Matoušek and U. Wagner, “New constructions of weak epsilon-nets,” presented at the SoCG: Symposium on Computational Geometry, 2003, pp. 129–135.
Matoušek J, Wagner U. 2003. New constructions of weak epsilon-nets. SoCG: Symposium on Computational Geometry, 129–135.
Matoušek, Jiří, and Uli Wagner. New Constructions of Weak Epsilon-Nets. ACM, 2003, pp. 129–35, doi:10.1145/777792.777813.