{"entities":{"Q1244819":{"pageid":1255569,"ns":120,"title":"Item:Q1244819","lastrevid":69977262,"modified":"2026-04-13T11:36:42Z","type":"item","id":"Q1244819","labels":{"en":{"language":"en","value":"The complexity of finding fixed-radius near neighbors"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3581611"}},"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":"Q1244819$C488A899-AD12-473C-9739-14AB268585C0","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"815d0b334f1f9fbb008830cc97e7993001cc31f8","datavalue":{"value":{"text":"The complexity of finding fixed-radius near neighbors","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1244819$68C84693-4531-4E03-B983-DB299FE6ED07","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"b5bdc45b46901a2591ffacfe5ff76cad6be21d1c","datavalue":{"value":"0373.68041","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1244819$AA143020-C54B-42A5-98F4-0F5E22AA4A05","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"478ab6f2c025b1770a2702d64ffbe7d40c42832f","datavalue":{"value":"10.1016/0020-0190(77)90070-9","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1244819$9AA7FF19-C918-4A10-9415-81D8D80B4411","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"1ea08fa1ad13c29c68cbbfed38868a84cd593791","datavalue":{"value":{"entity-type":"item","numeric-id":1134521,"id":"Q1134521"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1244819$3431B599-843A-4AC3-B2FF-FB9E8677ED6B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"2ae8fbc12112304621d124474d147524026b45b4","datavalue":{"value":{"entity-type":"item","numeric-id":1216950,"id":"Q1216950"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1244819$448EDE21-4E2D-4775-A6C7-36436CE7EF4C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"3e640a9d1ca8feefdf4bebe56a4b2897f75b8e54","datavalue":{"value":{"entity-type":"item","numeric-id":1244818,"id":"Q1244818"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1244819$388394D0-96F0-4E90-9BB1-AA3109E53BAB","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"52fa7d44b58d0511cb8993765bd916aef86052d8","datavalue":{"value":{"entity-type":"item","numeric-id":63092,"id":"Q63092"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1244819$1E9DE314-3A90-4FEB-9D49-E3F5A1AB953E","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"a49472451190faf858f564fafd4bcba399999753","datavalue":{"value":{"time":"+1977-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":"Q1244819$8D8017AD-AD1C-4514-8CE6-60E563406A31","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"979f9fdd1d39bcdbdfe2524e37172063b29f40d1","datavalue":{"value":"Given a finite set \\(S\\) of \\(N\\) points in \\(k\\)-space, and a positive radius \\(\\delta\\), the ``fixed-radius near neighbors problem'' calls for finding all pairs of points which are within the specified distance \\(\\delta\\) of one another. This problem arises in such applications as molecular graphics, density estimation, and cluster analysis. In this paper we present and analyze algorithms for solving the fixed-radius near neighbors problem when the distances between points are measured by the \\(_\\infty\\), or ``maximum coordinate'', metric. The number of fixed radius near neighbor pairs in a point set can vary between zero and \\(N\\cdot(N-1)/2\\). Any algorithm which correctly finds all near neighbors must therefore take at least \\(O(N^2)\\) time in the worst case, if the complexity is measured only as a function of the input size \\(N\\).    In this paper we present an algorithm and measure its complexity as a function of \\(N\\) (the input size) and \\(F\\) (the number of points found, or the output size). We show that all \\(F\\) near neighbors can be found in \\(O(N\\log N+F)\\) time on a RAM/RASP machine using only linear storage. The analysis of the algorithm is unusual in that the complexity is measured as a function of both input and output sizes, where the output size is unknown beforehand.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1244819$F21321B5-8174-400E-AC97-3F36C0A838BE","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6be78f1bad1f2f19058dbde65eb124c0430a7d27","datavalue":{"value":"68W30","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1244819$D6BCF79A-BCEC-4732-810B-19E669207141","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a7ddaa80bf0a693a36c1113ff6b7ad576f729940","datavalue":{"value":"68W40","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1244819$0FFA7BDE-3C8C-423E-A36E-DD6DC0CBD57D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"48a59f52dcfcc38cd6697e0ef07319031311895b","datavalue":{"value":"62H30","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1244819$F36B31B5-E12A-4B82-9800-FFC2D695ED68","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"3866ee96b4b7ddfafdb7b788eaa87fdd43bbf474","datavalue":{"value":"62G05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1244819$1035314E-5208-4E30-87B1-2724E3191013","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"9b78776a56fc28cdd893baa47605a105412b838a","datavalue":{"value":"68Q45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1244819$25E81D12-3830-4A84-9E63-AF344F0DB835","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"ad2c75a3b460f71ea9f7e0650bada5b94b5f51d3","datavalue":{"value":"3581611","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1244819$102DBAD7-49F4-443E-ACB7-E83F86851984","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f6badf9ee3fa9ca44c69281c1a27636872483275","datavalue":{"value":"fixed-radius near neighbors problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1244819$ED930BED-F6A1-4293-9423-D9D17514683C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"48ddf43eca498c7e7087cd696beb82ea63925320","datavalue":{"value":"algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1244819$98846A32-3595-4646-A846-B4A483B32DD3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4ec171027d1650ccf5b7f14821b846bd5dc75680","datavalue":{"value":"complexity measure","type":"string"},"datatype":"string"},"type":"statement","id":"Q1244819$4163A833-2D2B-4A47-8B7A-00E494695E69","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"61cfcfa67e9a3648b99e146ee6b2cd7a1fdfff1a","datavalue":{"value":"complexity measured as function of both input and output sizes","type":"string"},"datatype":"string"},"type":"statement","id":"Q1244819$81E73F98-36DF-4CD6-9E17-D4519CDC9149","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"ff60798827be371630f94654609e5d6876ae534b","datavalue":{"value":"Q29394334","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1244819$9D0C594B-19FB-471D-AABA-D8DA2BBD4634","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":"Q1244819$E049AD2E-5606-4DAF-846C-E4B7AE32FBDF","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"f257fd1b2a69b546fc9c065646744dce1044241d","datavalue":{"value":"https://doi.org/10.1016/0020-0190(77)90070-9","type":"string"},"datatype":"url"},"type":"statement","id":"Q1244819$03A73CCE-1E8D-4127-AE7B-650007B82A0D","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"702469fd1161106604f46cbd6023480003f54e51","datavalue":{"value":"W1976455030","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1244819$27084529-CE0F-4AC2-99AB-5E6A57588F60","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"340ea97c0f2f383d364057042ebc9f9438fcc85a","datavalue":{"value":{"entity-type":"item","numeric-id":4091421,"id":"Q4091421"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1244819$82CCC384-EE74-4F81-BBD5-6FAC12429577","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"49b7557b673baecad0ec34997bfbd86b0c9130bd","datavalue":{"value":{"entity-type":"item","numeric-id":4140384,"id":"Q4140384"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1244819$52A52693-BDCD-48A3-81D7-AD26BFE20FBB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a634cbc29683300650d9989a01808c0a4931ead5","datavalue":{"value":{"entity-type":"item","numeric-id":4398780,"id":"Q4398780"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1244819$69E67C79-06C9-43C5-A197-14B0CA463494","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a3e32cd00e50889ce6fdac19be614a9be1a54020","datavalue":{"value":{"entity-type":"item","numeric-id":4164569,"id":"Q4164569"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1244819$EE324389-FC31-4AA1-B296-32510865A70D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4730b379b7e9a219f54e79f38e4804893df74cc4","datavalue":{"value":{"entity-type":"item","numeric-id":1230653,"id":"Q1230653"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1244819$A13CFE91-45B8-479E-8D82-2E8CF04B1B56","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a834ed88eac251ad09266e978a8fbaddb9bf08b3","datavalue":{"value":{"entity-type":"item","numeric-id":5681016,"id":"Q5681016"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1244819$E5F39708-67D9-4970-BB7C-EDF8E4976DD9","rank":"normal"}],"P1643":[{"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":"355ae6257f0bfb4713ed3c76856f6ca63192f776","datavalue":{"value":{"amount":"+0.8754349946975708","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":"Q1244819$36E530BF-EE27-40FA-BFD6-25055F559C2B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"634f11fd381d11b65a5253ef0b2eefdcab7020d0","datavalue":{"value":{"entity-type":"item","numeric-id":4527028,"id":"Q4527028"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d92a1ad770e29a0112746827f36c0cb59d5504e9","datavalue":{"value":{"amount":"+0.8727263808250427","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":"Q1244819$94EFC8AB-A52F-4E0F-8525-D7BB286B8FD2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bfb88cb39cdcc8ed46f9ef721b07e5539247e268","datavalue":{"value":{"entity-type":"item","numeric-id":916423,"id":"Q916423"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"45740caad9adb3d1ae7351621584420cb461e4dc","datavalue":{"value":{"amount":"+0.8577295541763306","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":"Q1244819$C282C2BC-63E1-4B3C-A87D-F9673048EFE3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"57e46f0ebd84c14f577af3a39a0ac001c46678e7","datavalue":{"value":{"entity-type":"item","numeric-id":1115187,"id":"Q1115187"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b623ae980f1f3837f734c52e69cdf67a1376e7c0","datavalue":{"value":{"amount":"+0.8318699598312378","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":"Q1244819$F19041A9-F994-42AA-9C18-35B5D4AD6D3F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"382ffe4c77f7c25026365e07f00484d5be3ceebf","datavalue":{"value":{"entity-type":"item","numeric-id":4016892,"id":"Q4016892"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"db3baf43d71e35f4779d246f169424f654c8a8af","datavalue":{"value":{"amount":"+0.8299770355224609","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":"Q1244819$6DF6DC29-0DA7-4B14-B735-D732314E4C47","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"The complexity of finding fixed-radius near neighbors","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/The_complexity_of_finding_fixed-radius_near_neighbors"}}}}}