{"entities":{"Q1062772":{"pageid":1073524,"ns":120,"title":"Item:Q1062772","lastrevid":66062430,"modified":"2026-04-12T07:16:55Z","type":"item","id":"Q1062772","labels":{"en":{"language":"en","value":"Optimal solutions for a class of point retrieval problems"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3915670"}},"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":"Q1062772$C3E87390-C025-4E12-98E7-3DAB042DEE86","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"13eeb21beeb39243bcb9a58ac4de9cc6265bd143","datavalue":{"value":{"text":"Optimal solutions for a class of point retrieval problems","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1062772$60D062FD-BEC3-4308-B49F-BBB12F01C8E7","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"9cfffb6f34f36e77ac26ed211bdcb6f76ddf50b9","datavalue":{"value":"0573.68063","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1062772$77A9823C-A968-4702-BCD3-9BBEB0F810DD","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"8b354bc86a0d5fa15559246e546a21ed774ee93b","datavalue":{"value":"10.1016/S0747-7171(85)80028-6","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1062772$92A95D8B-7993-484E-8BFF-F32A470D4463","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"ea72303f92787da89554ee5fa15621068821a762","datavalue":{"value":{"entity-type":"item","numeric-id":99061,"id":"Q99061"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1062772$573DF993-D83A-4878-8967-EB7EF0C7618F","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"3c94df5c9af0ede578c52141befd29044de13172","datavalue":{"value":{"time":"+1985-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":"Q1062772$662D2EF7-BED6-4535-9BA4-3D291093B480","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"70e4d22c05f90abc861394b3ef57e0649fa6c8e2","datavalue":{"value":"Let P be a set of n points in the Euclidean plane and let C be a convex figure. We study the problem of preprocessing P so that for any query point q, the points of P in \\(C+q\\) can be retrieved efficiently. If constant time suffices for deciding the inclusion of a point in C, we then demonstrate the existence of an optimal solution: the algorithm requires O(n) space and \\(O(k+\\log n)\\) time for a query with output size k. If C is a disk, the problem becomes the well-known fixed-radius neighbour problem, to which we thus provide the first known optimal solution.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1062772$65A9207E-0CF0-48EB-9BF0-052684461E46","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"a762d1a2468ec8882180d0d1124f12b94f8eb1b0","datavalue":{"value":"68P20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1062772$2567B647-136A-4087-AC00-7A289DE1D00F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1062772$C2F52D11-8494-4708-BE73-E21B2788657D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"e5762e9b09407c15760c5fa5cac71c82c32bf230","datavalue":{"value":"52A10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1062772$23BE2E47-AF90-4F93-92C5-0B701C280CF9","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"4f8090a012df8fb7dc3efcd949476c99a1194ee8","datavalue":{"value":"3915670","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1062772$39683672-C4EC-4BD5-861D-202CF8912F0E","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"56cdb598c0821820a3654ff052247a213a065097","datavalue":{"value":"query point","type":"string"},"datatype":"string"},"type":"statement","id":"Q1062772$56EC41C9-6DC0-4F8C-8283-51F7F2AF0EC1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c1f392b4769e80a59d02298569be0683f08669c3","datavalue":{"value":"fixed-radius neighbour problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1062772$BBD149E0-D45F-4A34-BA57-B9D6E8BDF87C","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"5ad91bd4a1378a015ef9d0cfb2ca621b16347f71","datavalue":{"value":{"entity-type":"item","numeric-id":525971,"id":"Q525971"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1062772$8D3ED027-FE8F-4EE0-A66B-A765A0772F5F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"a06f7d76e1dbfa89a80e5d40561052d9e137ca58","datavalue":{"value":{"entity-type":"item","numeric-id":242843,"id":"Q242843"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1062772$4215845B-BC45-40CD-BD85-787F198961CD","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":"Q1062772$EA697F89-6428-4E02-9FDC-1D8BFE4E085B","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"f9151d6d4e2ff521df32794dada1fcf7423a6bb2","datavalue":{"value":{"entity-type":"item","numeric-id":1253102,"id":"Q1253102"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1062772$E8FD87C3-64D5-48CA-8AFA-2D60533265CB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a876917bdf78b8c50d4a6a59c404fb7842a2db3e","datavalue":{"value":{"entity-type":"item","numeric-id":1165007,"id":"Q1165007"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1062772$89372201-C6A6-48E1-A2E5-022C6EE1F39B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5bdd6d4dd66b2a42826f757d952178bfd95cd7fa","datavalue":{"value":{"entity-type":"item","numeric-id":3656974,"id":"Q3656974"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1062772$A122B249-823C-41DF-98BB-1633637B5543","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":"Q1062772$67E14C0A-3A41-44D6-B924-0E7E17A7764F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ff81489e80366438468bf6dfe10c7a159bc3ea8c","datavalue":{"value":{"entity-type":"item","numeric-id":4057549,"id":"Q4057549"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1062772$DB56B595-65F3-40AE-A3AB-017A99E2D329","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"db8343e526f156f1469a28b5688ff6513e9b7246","datavalue":{"value":{"entity-type":"item","numeric-id":3678701,"id":"Q3678701"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1062772$0DD1185F-B643-40C6-A305-D458EE0A751D","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"56bdcad9ee48051fa3a1089996f6eebd9457aab2","datavalue":{"value":{"entity-type":"item","numeric-id":3687755,"id":"Q3687755"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d8d9d1472e2da1dd57e6cd0835ed1fb1732d9f9d","datavalue":{"value":{"amount":"+0.9983330368995668","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":"Q1062772$AEB13E9F-3049-4FBD-BB2A-19CE63E45062","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"503f183f101d49472c5e066fd4f35d21f996546e","datavalue":{"value":{"entity-type":"item","numeric-id":4294714,"id":"Q4294714"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6c9eb39018b3ae96dbb59388f9a6d92b005ad75d","datavalue":{"value":{"amount":"+0.8213807940483093","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":"Q1062772$65005CFC-840A-4BAE-B571-05C60AD84221","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"faeed16a2cb130df085ce7d96f35c7be17f75efd","datavalue":{"value":{"entity-type":"item","numeric-id":1182100,"id":"Q1182100"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8fdff727dfd640ee5fc06d347aa57a236efdc264","datavalue":{"value":{"amount":"+0.815915584564209","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":"Q1062772$927AE35C-3934-4B7B-BFFF-40EBD6F0D988","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fd155f4d82d6461a977657e2bfefd67578e91ab7","datavalue":{"value":{"entity-type":"item","numeric-id":3777466,"id":"Q3777466"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fe860334c30cdf660cd8390cf29542d5974bf4bb","datavalue":{"value":{"amount":"+0.7594360113143921","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":"Q1062772$1C115668-5435-465C-BF07-FC6AF55806F9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b79114ee0c48059a3335ce68ab01b90053f6505f","datavalue":{"value":{"entity-type":"item","numeric-id":3719869,"id":"Q3719869"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c4c31cafd13185ee3dd7ccd91dcc5acb8f376625","datavalue":{"value":{"amount":"+0.7589846253395081","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":"Q1062772$170E10A3-5FD8-4015-BF80-819BF948F135","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Optimal solutions for a class of point retrieval problems","badges":[]}}}}}