{"entities":{"Q1715082":{"pageid":1725823,"ns":120,"title":"Item:Q1715082","lastrevid":72219003,"modified":"2026-04-14T03:24:42Z","type":"item","id":"Q1715082","labels":{"en":{"language":"en","value":"A simple proof of optimal epsilon nets"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7011215"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1715082$265B65F8-A9AF-485E-85F0-58EB36E5C270","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"892bbc94ddbbe2e3ff8d625aef5e5422f27e0a7e","datavalue":{"value":{"text":"A simple proof of optimal epsilon nets","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1715082$954F5AF6-3CB2-4932-AD7D-A3D10EC33469","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"82849cd4a1c0705ed4cd9a0681aa8dae42710965","datavalue":{"value":"1424.52020","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1715082$2B0BEBC1-7A4B-40D4-B4A5-2521823C71A9","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"73ed7dc5dc423f28adfd81f86427abf314dba4fd","datavalue":{"value":{"entity-type":"item","numeric-id":265721,"id":"Q265721"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1715082$11208087-B949-45E4-B214-9DF62784AFCB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"1a19f55276cf3e77185b1927592b3025892da801","datavalue":{"value":{"entity-type":"item","numeric-id":294553,"id":"Q294553"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1715082$634D97A4-417E-40CC-B691-B2B3005D98F7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"08fb9b36ab3f54b20702b33cd0ebcef73689c3a7","datavalue":{"value":{"entity-type":"item","numeric-id":294554,"id":"Q294554"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1715082$B0AEB2E6-AFF1-4C95-AD1C-202F64D8F57B","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"a87e84d22579e69c48ca0a6d828473db4dde3dd6","datavalue":{"value":{"entity-type":"item","numeric-id":168579,"id":"Q168579"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1715082$B92713D7-BF19-43F8-93C6-39F20927B1E4","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"3f4145805478faad59761c3ff4a8cc3fff513172","datavalue":{"value":{"time":"+2019-02-01T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1715082$0DFC6613-2F20-4D5E-A9F6-8831C49B1AF1","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"c589007f827f4ae2db40bd89d453a12e92a759a5","datavalue":{"value":"Given a set system $(X,\\mathcal{R})$ and any $Y \\subseteq X$, $\\mathcal{R} \\vert_Y$ is defined to be $\\{ Y \\cap R \\mid R \\in \\mathcal{R}\\}$. The VC-dimension VC-$\\dim (\\mathcal{R})$ of $\\mathcal{R}$ is the size of the largest $Y \\subseteq X$ for which $\\mathcal{R} \\vert_Y =2^Y$.\\par For $\\varepsilon > 0$, an $\\varepsilon$-net for a set system $(X,\\mathcal{R})$ is a set $N \\subseteq X$ such that $N \\cap R \\ne \\emptyset$ for all $R \\in \\mathcal{R}$ with $\\vert R\\vert \\geq \\varepsilon \\vert X\\vert $.\\par A set system $(X,\\mathcal{R})$ has shallow-cell complexity $\\varphi_{\\mathcal{R}}(\\cdot,\\cdot)$ if for any $Y \\subseteq X$, the number of subsets in $\\mathcal{R}\\vert_Y$ of size at most $\\ell$ is $\\vert Y\\vert \\cdot \\varphi_{\\mathcal{R}}(\\vert Y\\vert ,\\ell)$.\\par The size of the smallest $\\varepsilon$-nets for set systems has been settled in terms of shallow-cell complexity. The authors give a short proof of this result based on the $\\varepsilon$-net bound of \\textit{D. Haussler} and \\textit{E. Welzl} [Discrete Comput. Geom. 2, 127--151 (1987; Zbl 0619.68056)] together with the packing lemma of \\textit{D. Haussler} [J. Comb. Theory, Ser. A 69, No. 2, 217--232 (1995; Zbl 0818.60005)]. More precisely, the authors prove the following. Let $(X,\\mathcal{R})$, $\\vert X\\vert = n$, be a set system with VC-$\\dim (\\mathcal{R}) = d$ and shallow-cell complexity $\\varphi_{\\mathcal{R}}(\\cdot,\\cdot)$, where $\\varphi_{\\mathcal{R}}(\\cdot,\\cdot)$ is a non-decreasing function in the first variable. Then there exists an $\\varepsilon$-net for $\\mathcal{R}$ of size $O(\\frac{1}{\\varepsilon} \\log \\varphi(\\frac{8d}{\\varepsilon},24d) + \\frac{d}{\\varepsilon})$.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1715082$EAFA3E8D-2052-4CEC-979D-2C5258124AC8","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"eab1c57f4c7b158bf2191a8e754d0819459c7a21","datavalue":{"value":"52C45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1715082$CF8011E6-9F68-4B36-9611-D03EFBA4D1A3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"1ad1bf428b79a0176d62afa9a160b2a17f8d9ea9","datavalue":{"value":"05D15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1715082$328EDF55-2817-44C2-967B-E565BF521F2A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"2762df744fec88c5da60f696833f02907bd4417a","datavalue":{"value":"52B55","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1715082$A38D6840-94D6-44F7-ADD2-F386FE3BF49B","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"312f1f4b17a82ac324e47a1e2651b8d820fb66b8","datavalue":{"value":"7011215","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1715082$7CDC5829-35EB-4EB0-8109-E9E38741B0CE","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"467b25a1ffe6f7ce35e935740d072a9a5130e16c","datavalue":{"value":"set system","type":"string"},"datatype":"string"},"type":"statement","id":"Q1715082$1C9B5681-3EB9-4D74-9A3D-F7B81A6BA2F0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"40dfb25b9dc7aa9fd8093db5d6b661320a1cf8af","datavalue":{"value":"VC-dimension","type":"string"},"datatype":"string"},"type":"statement","id":"Q1715082$2E759289-14CE-4AF6-BE1B-C3458EEDB33B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"103307c618e570177020ca2dee3ec7f4d637b23b","datavalue":{"value":"$\\varepsilon$-net","type":"string"},"datatype":"string"},"type":"statement","id":"Q1715082$85F43131-08B5-48F1-AA8E-BCCB5C8BFC2A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"44fec6ff09caa0b371078ac3fb7d463589947d26","datavalue":{"value":"shallow-cell complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1715082$65EDD267-91F3-4F42-A508-D78FDA33E45E","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1715082$10B992D6-4802-4D5D-A734-CE0DE84CBF90","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"b814857277a261bb20425f292ec33cc6b7f6d5eb","datavalue":{"value":"https://doi.org/10.1007/s00493-017-3564-5","type":"string"},"datatype":"url"},"type":"statement","id":"Q1715082$2E0D4161-209C-4082-A43D-548EE1D6E931","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"a11f0ee600948f631c7f55df9491911135cd2e6c","datavalue":{"value":"W2587329907","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1715082$D1E99B38-FDAD-4515-9DAC-A29122DFF0CE","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"666c45afb30c1d4c867ab4131e2a2fef4ca14348","datavalue":{"value":"10.1007/S00493-017-3564-5","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1715082$E66AC77A-A975-4AAB-B539-4768B9EF6BE8","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5b650609d49c365e490e0c3f0194c68e3a3a5b7e","datavalue":{"value":{"entity-type":"item","numeric-id":2415378,"id":"Q2415378"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"93575ec3b9f87433bd6eaaad608984a07fd1cb62","datavalue":{"value":{"amount":"+0.849551","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1715082$0B6D709E-8177-4F29-AE9B-5BF9DA34333B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ef952840ce39d56a84d41ab1afda41eddd1f7fd7","datavalue":{"value":{"entity-type":"item","numeric-id":3132890,"id":"Q3132890"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a360f0fe59b38516de42987858918ae9aeac50a9","datavalue":{"value":{"amount":"+0.7963058","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1715082$0DE0371A-F1ED-4AE4-92CB-0798BCAAA352","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"059b5092322717844aee1da1e6ac61f3bbbdbf8f","datavalue":{"value":{"entity-type":"item","numeric-id":4604388,"id":"Q4604388"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7679c0143a81c4e19b045f1667493bfe02f13d52","datavalue":{"value":{"amount":"+0.7906158","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1715082$3D208C3D-C258-43D7-9B56-6DD4AF75AD84","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"31ed539f44d0f72eea971ba71294b4123fce6ca2","datavalue":{"value":{"entity-type":"item","numeric-id":4580113,"id":"Q4580113"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5a52133ec7b6a9be80885c963541fb6a238f5919","datavalue":{"value":{"amount":"+0.782675","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1715082$9A804595-7B70-46F8-868B-55A8F52A456B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b892164322f4345ac5f78e97b4bc94b2ed163b5d","datavalue":{"value":{"entity-type":"item","numeric-id":728497,"id":"Q728497"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8c146bc6ded5ed4eaacb75199a1db8623a9a3409","datavalue":{"value":{"amount":"+0.7509499","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1715082$C7905046-BFE5-46F8-81AA-E4A5C5206222","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e8050995e4f6a869773e0bda8ec150a2d3c19c4d","datavalue":{"value":{"entity-type":"item","numeric-id":5368679,"id":"Q5368679"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ee213e3a918b120984195496c3839bcbd1a39e19","datavalue":{"value":{"amount":"+0.7460461","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1715082$AB08405A-C2A0-4CF6-BF60-1C399C2055B0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"10f14ff3593b0c8551b7cae3a747e4bb39a2ee85","datavalue":{"value":{"entity-type":"item","numeric-id":5091247,"id":"Q5091247"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c972303d577f8c660225d79b3925c3c01161fcea","datavalue":{"value":{"amount":"+0.7413858","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1715082$AE1A29C9-3A27-4022-B7E5-BAE1B36CA87F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a8db761e3786b0aba247f2f4006f9174de048be4","datavalue":{"value":{"entity-type":"item","numeric-id":1369741,"id":"Q1369741"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"20e58606d68810d278b2d7909946b85d7c4cf3d1","datavalue":{"value":{"amount":"+0.7078161","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1715082$D8492475-A5A4-4F59-89E1-A6141EF6F284","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"166e8388975ed1a886b11c3c03b74e033735d8be","datavalue":{"value":{"entity-type":"item","numeric-id":4289289,"id":"Q4289289"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"294220b49c39d864899282b193bf5a2f2eb0d458","datavalue":{"value":{"amount":"+0.6853412","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1715082$296B7F30-5103-4166-A3A3-BA4BCB28F822","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d96f8cce10dd415c833d5dae003444ea9b42f34e","datavalue":{"value":{"entity-type":"item","numeric-id":4208235,"id":"Q4208235"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3bb51488477edc4c993f060a176afdea6caf5040","datavalue":{"value":{"amount":"+0.67933714","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1715082$6CAC032C-F4AA-494C-9DE3-622FD6A37315","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"A simple proof of optimal epsilon nets","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/A_simple_proof_of_optimal_epsilon_nets"}}}}}