[{"type":"journal_article","abstract":[{"lang":"eng"}],"issue":"2","publist_id":"4500","extern":1,"_id":"2425","publication_status":"published","status":"public","intvolume":" 32","author":[{"first_name":"Jiří","last_name":"Matoušek"},{"id":"36690CA2-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-1494-0568","first_name":"Uli","last_name":"Wagner"}],"dini_type":"doc-type:article","date_created":"2018-12-11T11:57:35Z","date_updated":"2021-01-12T06:57:24Z","volume":32,"dc":{"date":["2004"],"relation":["info:eu-repo/semantics/altIdentifier/doi/10.1007/s00454-004-1116-4"],"publisher":["Springer"],"title":["New constructions of weak ε-nets"],"source":["Matoušek J, Wagner U. New constructions of weak ε-nets. Discrete & Computational Geometry. 2004;32(2):195-206. doi:10.1007/s00454-004-1116-4"],"rights":["info:eu-repo/semantics/closedAccess"],"creator":["Matoušek, Jiří","Uli Wagner"],"description":["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(ε-dpolylog(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/ε))."],"identifier":["https://research-explorer.ista.ac.at/record/2425"],"type":["info:eu-repo/semantics/article","doc-type:article","text","http://purl.org/coar/resource_type/c_6501"]},"day":"01","month":"07","uri_base":"https://research-explorer.ista.ac.at","publication":"Discrete & Computational Geometry","citation":{"chicago":"Matoušek, Jiří, and Uli Wagner. “New Constructions of Weak ε-Nets.” Discrete & Computational Geometry. Springer, 2004. https://doi.org/10.1007/s00454-004-1116-4.","short":"J. Matoušek, U. Wagner, Discrete & Computational Geometry 32 (2004) 195–206.","mla":"Matoušek, Jiří, and Uli Wagner. “New Constructions of Weak ε-Nets.” Discrete & Computational Geometry, vol. 32, no. 2, Springer, 2004, pp. 195–206, doi:10.1007/s00454-004-1116-4.","ieee":"J. Matoušek and U. Wagner, “New constructions of weak ε-nets,” Discrete & Computational Geometry, vol. 32, no. 2. Springer, pp. 195–206, 2004.","apa":"Matoušek, J., & Wagner, U. (2004). New constructions of weak ε-nets. Discrete & Computational Geometry. Springer. https://doi.org/10.1007/s00454-004-1116-4","ista":"Matoušek J, Wagner U. 2004. New constructions of weak ε-nets. Discrete & Computational Geometry. 32(2), 195–206."},"quality_controlled":0,"page":"195 - 206","date_published":"2004-07-01T00:00:00Z"}]