{"entities":{"Q1089803":{"pageid":1100555,"ns":120,"title":"Item:Q1089803","lastrevid":69619173,"modified":"2026-04-13T08:14:40Z","type":"item","id":"Q1089803","labels":{"en":{"language":"en","value":"\\(\\epsilon\\)-nets and simplex range queries"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4005628"}},"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":"Q1089803$E4918FD9-D05D-435D-A21F-88062174CBA4","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"e088aa3f79ffe119eb10323075a29f25fe385732","datavalue":{"value":{"text":"\\(\\epsilon\\)-nets and simplex range queries","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1089803$06F29AA6-1B90-424C-998A-68342CC43628","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"3e076be34898b0b59bedf3368032e19d91390a17","datavalue":{"value":"0619.68056","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1089803$6EB39748-FCEC-4954-8ED1-CF684F37F54F","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"9f4ac7e971999c2e54ad4e3c14bf036cd5c5a74b","datavalue":{"value":"10.1007/BF02187876","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1089803$C28F6EA4-2855-4FCA-AAAF-5ECBAFB5F682","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"bd2d3ae090b22c3a641be4fedb72aeccd09f0d74","datavalue":{"value":{"entity-type":"item","numeric-id":676241,"id":"Q676241"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1089803$9553ED2D-BAB2-4C3E-8988-8357F1DCE164","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"ebde143434d63bb91413660f73ab09b4563fd56f","datavalue":{"value":{"entity-type":"item","numeric-id":1262764,"id":"Q1262764"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1089803$80497FD1-926F-4481-861F-80BFF3EE7AA0","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":"Q1089803$4CFF011B-F65B-4555-A754-1A0FBCF3E2D7","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"5ae48c61eed19d1e1e1f33f9255d5b329362d064","datavalue":{"value":{"time":"+1987-00-00T00:00:00Z","timezone":0,"before":0,"after":0,"precision":9,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1089803$DC98760D-66E1-463D-A72C-E3DBEBF8C83D","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"4530bee9a1a6efda1b78b2708cda56d28b54dd31","datavalue":{"value":"https://eudml.org/doc/131015","type":"string"},"datatype":"url"},"type":"statement","id":"Q1089803$1B2906EF-9E54-46C6-B2DF-A995193B66B8","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"0767a8253686191c19fcd6839001b5ff12c6753b","datavalue":{"value":"The main problem may be described as follows: given a set of n points in d-dimensional Euclidean space, find a data structure that uses linear storage such that the number of points in any query half space can be determined in sublinear time \\(O(n^{\\alpha})\\). A data structure with \\(\\alpha =d(d-1)/(d(d-1)+1)+\\gamma\\) for any \\(\\gamma >0\\) is exhibited. These bounds for \\(\\alpha\\) are better than those previously published for all \\(d\\geq 2\\) by \\textit{A. Yao} and \\textit{F. Yao} [A general approach to d- dimensional geometric queries. Proc. 17th Symp. Theory of Computing, 163- 169 (1985)].    Let X be a set and R be a set of subsets of X, which have a finite dimension in Vapnik-Chervonenkis sense [\\textit{V. N. Vapnik} and \\textit{A. Ya. Chervonenkis}: The theory of pattern recognition (Russian) (1974; Zbl 0284.68070)], A be a finite subset of X and \\(0\\leq \\epsilon \\leq 1\\). A subset N of A is an \\(\\epsilon\\)-net of A (for R) if N contains a point in each \\(r\\in R\\) such that \\(| A\\cap r| /| A| >\\epsilon\\). The authors prove that for \\(0<\\epsilon\\), \\(\\delta <1\\), if N is a subset of A obtained by \\(m\\geq \\max (4/\\epsilon \\log 2/\\delta,8d/\\epsilon \\log 8d/\\epsilon)\\) random independent draws, then N is an \\(\\epsilon\\)-net of A with probability at least 1-\\(\\delta\\). Using this result, a partition tree structure that achieves the above query time is constructed.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1089803$65E8F34F-3FAB-489B-B032-D9EB300E2A22","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"3f97694d44af155a68434cb72eabc6a4d5dd5227","datavalue":{"value":"68P10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1089803$FDB18729-FAD5-4221-A823-60E3FC782BB7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"ca61eab0925774aac3721bd45536bff0d1d0ff14","datavalue":{"value":"52A22","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1089803$D114EB4F-86C1-4B6D-BFD8-881A9EC35B24","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"4b7275e0d4b526075acce84a242d8537e929bb2d","datavalue":{"value":"60C05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1089803$E9A5F26C-A9CF-405D-B57A-61F964E4DE2A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"33db59d12518cc90bac7371d19f717ef52ec07bc","datavalue":{"value":"05B99","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1089803$E0994DFB-1D65-48A7-B32E-5D0554634FB7","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"4090ba7e5d6bd9608ba38e9c5efbe7277c1fce2e","datavalue":{"value":"4005628","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1089803$5D119D97-5A2C-4473-87A8-4B81718B7C2C","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a1b13e13eb20948696d0c2bcf55ae6cef683ba19","datavalue":{"value":"simplex range queries","type":"string"},"datatype":"string"},"type":"statement","id":"Q1089803$A48FE86A-214F-44CD-99A3-F18B4D3B6BA5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1d0d9d46e94d9dac2a966bd0bc7ac44de8c384fe","datavalue":{"value":"counting problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1089803$B7170EF7-57D2-4A40-9864-7CF00D1A1B20","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"be5e3500af73c496b19a0ff9e1df02f95da2c4bb","datavalue":{"value":"partitioning point sets","type":"string"},"datatype":"string"},"type":"statement","id":"Q1089803$80DA68E7-81F5-43EE-8F07-13C2A494194A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c25bc710e4a99b4ad5c06b7d722ebbdb9259ca1e","datavalue":{"value":"data structure","type":"string"},"datatype":"string"},"type":"statement","id":"Q1089803$0194BC52-51BC-4F6A-93A6-8A8738F0503B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f22e6b8810a7f8385a2aedb657105874224440d6","datavalue":{"value":"query half space","type":"string"},"datatype":"string"},"type":"statement","id":"Q1089803$ECD26E74-CACE-49CE-9489-11DC6F5E061D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5e225edfcfee3bc5b9c506e1bad6a172e676dfa3","datavalue":{"value":"sublinear time","type":"string"},"datatype":"string"},"type":"statement","id":"Q1089803$483D398B-B4F8-44C1-AC9B-314558642AC8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2e256eb45cf7415b1073be83bb7e544eb33c1c94","datavalue":{"value":"partition tree structure","type":"string"},"datatype":"string"},"type":"statement","id":"Q1089803$14BDBA1B-DA17-4258-BAB7-BC9162BB4D85","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"f4a94c0565fd5cd71c290df46f96d01dac28a658","datavalue":{"value":"Q54309840","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1089803$7CC646C7-788C-4A97-8324-8B85B3BB3BF1","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":"Q1089803$07A8047E-3D8C-498F-9A1D-1D73EACC8F95","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"598ea4d35182cf70c03e6fee9b193660ab4cfbfe","datavalue":{"value":{"entity-type":"item","numeric-id":1836212,"id":"Q1836212"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1089803$C689510A-2B91-4455-85CC-5E6A4B90114A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e9abc1c55505e1dd04a0add4b4ea95570e081496","datavalue":{"value":{"entity-type":"item","numeric-id":3687757,"id":"Q3687757"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1089803$DECC1327-2CBC-4AF0-A759-CF1714C75D86","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"080f9da3f76f9a31171911c17c1b7cda7ad8e4b3","datavalue":{"value":{"entity-type":"item","numeric-id":1256781,"id":"Q1256781"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1089803$901611EF-2357-4144-AC96-9B802DD2A8DA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"25b026e498c7466f890693e678f90760ff4b1c4e","datavalue":{"value":{"entity-type":"item","numeric-id":3772828,"id":"Q3772828"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1089803$61F1AE37-A39E-42BF-9A72-E63BC8DA97B2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"da92b4d12846aa1606fa89a7ac5ca00163d7fc64","datavalue":{"value":{"entity-type":"item","numeric-id":4720805,"id":"Q4720805"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1089803$F1086461-203B-423D-9CA4-FF087831A5AB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fcd35a1fd3af99492727136bdc8d532d451ebf6d","datavalue":{"value":{"entity-type":"item","numeric-id":1097038,"id":"Q1097038"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1089803$D40722AB-7C5C-4FA2-BF3A-4CAC342CE1D1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ff8fea9a5dba7c0c825c98a79aa7f9c13491987b","datavalue":{"value":{"entity-type":"item","numeric-id":5547252,"id":"Q5547252"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1089803$6A8AF3D0-4E72-4DF7-BC02-50307CBDD4A2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ed28daf112121dc08adf4ce72a073bd046e54847","datavalue":{"value":{"entity-type":"item","numeric-id":2556406,"id":"Q2556406"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1089803$2785EBFD-6FD7-4815-98D5-2BAFD21A6B3E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e55670eeffeb14e6ce51166fb8470acff9c12ef5","datavalue":{"value":{"entity-type":"item","numeric-id":5660314,"id":"Q5660314"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1089803$20A8E0F1-7EBA-4109-B426-A6E37FAAD455","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"87d73df5ed3139aebdca08c7e8b1075ae23062e8","datavalue":{"value":{"entity-type":"item","numeric-id":4770512,"id":"Q4770512"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1089803$116788D1-05C0-48B8-ACDB-B9DD170B7909","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2716313a77f67cac8a71aa75de62cce547513ce6","datavalue":{"value":{"entity-type":"item","numeric-id":1152158,"id":"Q1152158"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1089803$6AEBB521-9AF1-475A-A0D6-A82E2BD07286","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"50eda2043c94a0a2b9f4b5d31dd4f5e608303363","datavalue":{"value":{"entity-type":"item","numeric-id":3936209,"id":"Q3936209"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1089803$FAB01497-B190-4AAB-AF64-8F4EA39D07BC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c447778cd463b38391576260ed5e2ccdad1b984b","datavalue":{"value":{"entity-type":"item","numeric-id":3278735,"id":"Q3278735"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1089803$D022EC7A-8F85-4330-B76C-8AA7F14C610A","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"bdcb551411f630b8b9462ae685a07920df73d126","datavalue":{"value":"W2054459484","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1089803$6F1DF652-1C08-4C1D-A398-6612DD183193","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"836d78d17d41ede4c108a9e9179a0d5aacd50e5c","datavalue":{"value":{"entity-type":"item","numeric-id":914376,"id":"Q914376"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"50ba00b9f92605bfbc7d5058ec54919c6845acee","datavalue":{"value":{"amount":"+0.8695277571678162","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":"Q1089803$2FD67DC8-3594-4EFC-A1CC-DDFBF81DCF0F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"064bbb87effee1e41ea565a94482d6744aef2b13","datavalue":{"value":{"entity-type":"item","numeric-id":1184160,"id":"Q1184160"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a5771a4a07b812d43b37a71adc50ec6eeaeb75bf","datavalue":{"value":{"amount":"+0.8562840223312378","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":"Q1089803$6660C590-AEF2-42F4-913F-FAB033FE0309","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f8e79af431b4879bd210a03988a8c9cc140e7f23","datavalue":{"value":{"entity-type":"item","numeric-id":5172760,"id":"Q5172760"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f40ce774afff39236a2bc27e840c69370faedc8f","datavalue":{"value":{"amount":"+0.8560794591903687","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":"Q1089803$69FEAAFC-0066-4C34-BC6D-CE82FC1606FA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2a9514b9c182d3590e7fd60e845acb574b48e9c2","datavalue":{"value":{"entity-type":"item","numeric-id":5404461,"id":"Q5404461"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7968d87c95653bce504f01b3c75596743c07ff0c","datavalue":{"value":{"amount":"+0.8513466119766235","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":"Q1089803$860A3249-8D02-4C84-97ED-AFCE7747648F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5f60eae0b94a1959146617f33ec5ec2498e49842","datavalue":{"value":{"entity-type":"item","numeric-id":3138744,"id":"Q3138744"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"161c88eac72f226954e08d6f7200d9b9f4cc85ac","datavalue":{"value":{"amount":"+0.8493335247039795","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":"Q1089803$BC2FF914-E615-412B-822B-4AB0B63A09EE","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"\\(\\epsilon\\)-nets and simplex range queries","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/%5C(%5Cepsilon%5C)-nets_and_simplex_range_queries"}}}}}