{"entities":{"Q1762945":{"pageid":1773687,"ns":120,"title":"Item:Q1762945","lastrevid":55867060,"modified":"2026-02-20T16:03:59Z","type":"item","id":"Q1762945","labels":{"en":{"language":"en","value":"New constructions of weak \\(\\varepsilon\\)-nets"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 2133693"}},"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":"Q1762945$72942B10-FC13-4600-96D9-BB686577A6C5","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"4c45886c01d9a3e06935ec4d9a47f53a9072a43c","datavalue":{"value":{"text":"New constructions of weak \\(\\varepsilon\\)-nets","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1762945$216F9B5C-A2F3-4001-B6D8-CE7CC661DD57","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"7d5860f496cd25a6f6e31df3a329518ba30448a3","datavalue":{"value":"1104.68124","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1762945$FCCDAABE-CC31-45BF-B356-1ED2EAB794FA","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"a134b1b26c744b6d5062249cc5a2411ef0128dbc","datavalue":{"value":{"entity-type":"item","numeric-id":503251,"id":"Q503251"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1762945$66825C5E-84B1-4FC8-8158-F4B957E7B820","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"d5205659b4c2831752a8f8604dc5b3ce7b9439fa","datavalue":{"value":{"entity-type":"item","numeric-id":818688,"id":"Q818688"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1762945$831E86BE-76F8-45B7-9657-5D733C3969E2","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"b6f367138a9ac2b85113cfed5a6fd5bedcc8944c","datavalue":{"value":{"entity-type":"item","numeric-id":178842,"id":"Q178842"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1762945$33FA0B29-F437-4F8C-B8D5-335947A4FC6B","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"5596d9d431c014306023aa27a7b00ce60a426d45","datavalue":{"value":{"time":"+2005-02-11T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1762945$F77B5A69-1CB8-44CC-9083-4830FE008160","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"1fb38024a3aa1e9c50e3553b0e41b63baead6d92","datavalue":{"value":"A finite set \\(N \\subset \\mathbb R^d\\) is a weak \\(\\varepsilon\\)-net for an \\(n\\)-point set \\(X\\subset \\mathbb R^d\\) (with respect to convex sets) if \\(N\\) intersects every convex set \\(K\\) with \\(|K \\cap X|\\geq \\varepsilon\\). We give an alternative, and arguably simpler, proof of the fact, first shown by \\textit{B. Chazelle}, \\textit{H. Edelsbrunner}, \\textit{M. Grigni}, \\textit{L. Guibas}, \\textit{M. Sharir} and \\textit{E. Welzl} [ibid. 13, 1--15 (1995; Zbl 0822.68110)], that every point set \\(X\\) in \\(\\mathbb R^d\\) admits a weak \\(\\varepsilon\\)-net of cardinality \\(O(\\varepsilon^{-d}\\text{polylog}(1/\\varepsilon))\\). 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 \\(\\varepsilon\\)-nets in time \\(O(n\\ln(1/\\varepsilon))\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1762945$91FBFDA0-D5CB-4325-B63E-F90F74880449","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"159426a5937e62cfbbcc198dd4848ab52d6e715e","datavalue":{"value":"68U05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1762945$07D73A29-6792-4673-BF77-214A809C3CB5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"eab1c57f4c7b158bf2191a8e754d0819459c7a21","datavalue":{"value":"52C45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1762945$EFFB19A2-DCB8-4502-940B-6A4EF3E3E204","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"4bb357a48863dca6dfae0444520ec8897e1195d9","datavalue":{"value":"2133693","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1762945$21C777A5-3D89-46C6-A9E1-E52DB8BD5182","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":"Q1762945$4355E291-94C3-4BD8-AF87-CB67E4A329C4","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"dd4f7e3fb9efc9443b729c389a1b1982b3b603f3","datavalue":{"value":"https://doi.org/10.1007/s00454-004-1116-4","type":"string"},"datatype":"url"},"type":"statement","id":"Q1762945$C31DC9F7-925F-4913-A318-0AE1C56D1474","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"c8ed0608dac5dda57be0a3d66b5a15918c465da8","datavalue":{"value":"W2002642771","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1762945$6B2C9E8D-8A17-485F-A308-91867E31B960","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"3b281b0338066595ad73787006c5ed202b0e1ce8","datavalue":{"value":"10.1007/S00454-004-1116-4","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1762945$B36608CD-5B39-47E3-A5E9-E3878D37CE10","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"da362ca282fb596ee68827af2a75f8dd16bc45d6","datavalue":{"value":{"entity-type":"item","numeric-id":5361615,"id":"Q5361615"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0b5276994f0a9fa105129565422b63ff76b122a5","datavalue":{"value":{"amount":"+0.9726025462150574","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1762945$E8FC8644-0B86-4025-A55B-6952AE8598F9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"995c3bb40a7167f495a6bbafd7cc517b96a23d7d","datavalue":{"value":{"entity-type":"item","numeric-id":1346122,"id":"Q1346122"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"883f0e2cc4634adaf496017b7218086d97d25ddb","datavalue":{"value":{"amount":"+0.917781949043274","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1762945$1E94D81B-4833-4D1E-BA13-86CE1D032969","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f3936286d3ab4afc3c073ddb65d0b205b470af38","datavalue":{"value":{"entity-type":"item","numeric-id":1611071,"id":"Q1611071"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"08a20be5638edcc9bf65386b3d35d96585c39daf","datavalue":{"value":{"amount":"+0.8899986147880554","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1762945$02183CD1-B190-46EB-8705-299C3ECDBEFD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"028408920dda2bf9640f43a4a275407c50fbda29","datavalue":{"value":{"entity-type":"item","numeric-id":1025302,"id":"Q1025302"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9053ea9d7f9e0119cbda2a47c9fada93b78970ce","datavalue":{"value":{"amount":"+0.8899228572845459","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1762945$BF73BAC4-6641-4C63-9B11-E7424A444B68","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1762945","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1762945"}}}}}