{"entities":{"Q789903":{"pageid":791751,"ns":120,"title":"Item:Q789903","lastrevid":48683107,"modified":"2026-01-05T14:42:30Z","type":"item","id":"Q789903","labels":{"en":{"language":"en","value":"A counter example to a monotonicity property of k-d trees"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3846892"}},"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":"Q789903$AF3E833E-0B64-46D7-9F98-51369C312401","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"8d741375ded13bb57db6e9b96df414cacdb72779","datavalue":{"value":{"text":"A counter example to a monotonicity property of k-d trees","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q789903$B55DFEF3-61CD-4CA1-92EE-F6BD679D8225","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"77ebf9aed8e1a804a7a7ee2836c1b8bf0e34e9a8","datavalue":{"value":"0533.68066","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q789903$C2EF54A3-AB5E-4153-A4F4-1FE167B8E855","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"b970ba4c01e7790d867dd3738145e5e359d01443","datavalue":{"value":"10.1016/0020-0190(82)90099-0","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q789903$782D324D-FE12-4833-8BD4-8029EFB5CFC7","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"6b3a7c166fcef96513cc70d2793bfa5042d279ba","datavalue":{"value":{"entity-type":"item","numeric-id":789901,"id":"Q789901"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q789903$E4BE854F-2F27-4210-83EC-AD316E9FB89F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"1aea9fdeb9eb4d96ac94c7cb11760ddb650d05b7","datavalue":{"value":{"entity-type":"item","numeric-id":789902,"id":"Q789902"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q789903$619FECDE-28E7-440E-BA1C-EACF5386B487","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":"Q789903$2A2AA69C-90B5-41E9-A14D-11D06D124E94","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"47f57cd36df9e30d446df3867dc3917e4ea74654","datavalue":{"value":{"time":"+1982-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":"Q789903$695B202C-39EC-4AE0-B59D-3B589EF16CBC","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"cbb788476c65d46a69fc8d78a9d079fe720cb95b","datavalue":{"value":"In Commun. ACM 18, 509-517 (1975; Zbl 0306.68061) \\textit{J. L. Bentley} introduced k-dimensional binary search trees (abbreviated k-d tree) as a data structure for storing multikey records. The k-d tree, as defined in this paper, is a binary tree in which all the records are stored at external nodes, while each internal node has a discriminator field (indicating one of the k keys), a partition value (key value for the key chosen by the discriminator) and pointers to the left and right sons. The defining property of a k-d tree is that for any internal node x, if m is the discriminator value and M the partition value at x, then all records (within the subtree rooted at x) with m-th key values smaller or equal to M are located in the left subtree of x, while all records with m-th key values greater than M belong to the right subtree. The authors present an algorithm, of the dynamic programming type, for constructing an optimum k-d tree; their algorithm runs in \\(0(n^{2k+1})\\) time and it takes \\(0(n^{2k})\\) space. Further, the authors formulate a generalized version of the monotonicity property for 1-dimensional optimum binary search trees [\\textit{A. Itai}, SIAM J. Comput. 5, 9-18 (1976; Zbl 0328.68040); \\textit{D. E. Knuth}, Acta Inf. 1, 14-25 (1971; Zbl 0233.68011)] and show that it does not hold in the general setting.","type":"string"},"datatype":"string"},"type":"statement","id":"Q789903$EC7C562F-BD5C-46A6-8EB2-4FE1151D5E3E","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"3f97694d44af155a68434cb72eabc6a4d5dd5227","datavalue":{"value":"68P10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q789903$688AD452-DA84-4601-AA9A-402063FB1522","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q789903$67EC3672-4EB5-4EE0-9D96-6D0DF4F3FAF3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d5da87a72c21717089feda882f568938059a9d84","datavalue":{"value":"05C05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q789903$CF4FFC0A-65BB-4ABA-95B8-D2F6A126D9B0","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"93707b8809ee145ee4640320918c386c6f358445","datavalue":{"value":"3846892","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q789903$9F873D2A-4D44-418F-924A-A2DD40BE51A2","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c2969339e41c46614b3db44c62ea26cd9b740a45","datavalue":{"value":"multidimensional binary search tree","type":"string"},"datatype":"string"},"type":"statement","id":"Q789903$9B21BC35-9FDD-4B85-AE50-0A1B5D982EFB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cb78c0a1893dd8ffc725b56a510330660485599a","datavalue":{"value":"optimum tree","type":"string"},"datatype":"string"},"type":"statement","id":"Q789903$DF9AC811-FD53-4D21-AE58-662FC1270CDC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"fbe8c80328f59a1b0274b52bf73e7c971d27197d","datavalue":{"value":"monotonicity property","type":"string"},"datatype":"string"},"type":"statement","id":"Q789903$36F58174-209F-4DE6-BFA7-77E841F7A106","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3c4e6f5ee3eb96ede7e096aad916387ba8743a62","datavalue":{"value":"dynamic programming algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q789903$63B5B023-517F-46B7-900B-80B29AE9E257","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"cb3a3ba65440da04d49f30062ed2e12f784ddb41","datavalue":{"value":{"entity-type":"item","numeric-id":235683,"id":"Q235683"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q789903$2E736EE5-1942-43B2-93D0-2880E7FF046C","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":"Q789903$6FE11D9D-C5CF-4CD1-9B90-D50458914738","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"ee9a41baf562b53104fe55d6933fcec3b00fa24b","datavalue":{"value":"https://doi.org/10.1016/0020-0190(82)90099-0","type":"string"},"datatype":"url"},"type":"statement","id":"Q789903$91B2786E-D981-4C28-8A1F-006FE25A29ED","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"f2d5af1263236d30b9d1ef2202f0c733e2b8b5aa","datavalue":{"value":"W2015488612","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q789903$1E231478-DE4F-4639-A456-B33B799861C0","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"5eb040f4f53698848aa91aa2991b3af0b6cf962f","datavalue":{"value":{"entity-type":"item","numeric-id":4062679,"id":"Q4062679"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q789903$EA7603F9-52EA-4E5E-BDEC-9588C1E34990","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ebfb063389676a32c32c9a9730fa309059ea3a51","datavalue":{"value":{"entity-type":"item","numeric-id":4094387,"id":"Q4094387"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q789903$4C9442D6-B4A5-4743-A4B2-E6A8460A9E11","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c4fd2399a3704cf83726a1162abe2d51c058ed2e","datavalue":{"value":{"entity-type":"item","numeric-id":2551314,"id":"Q2551314"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q789903$FDC21CC5-ADDA-49F0-83CC-B1434025D5CD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4f6d258a646c12940112dae7b62e791e61d32ddf","datavalue":{"value":{"entity-type":"item","numeric-id":3901002,"id":"Q3901002"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q789903$79A868EF-1B9C-497D-96FF-7ED868A496BC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a8bac91599ec403c1027546b4a2b26827f5d5a10","datavalue":{"value":{"entity-type":"item","numeric-id":1138383,"id":"Q1138383"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q789903$F9CEA872-9CE6-417A-BDB5-4839593F8306","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"32f92e9ff6bb2442bc50072c2abe5a34de870ba0","datavalue":{"value":{"entity-type":"item","numeric-id":384731,"id":"Q384731"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8304bd90b57858c71bab86a2a4fef6edd1c4f502","datavalue":{"value":{"amount":"+0.7720906734466553","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":"Q789903$48A1CD9A-B56A-4DCD-8948-D28B505FBD99","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"14ec020f03f1f3eec9baa2686defb7e9635231c5","datavalue":{"value":{"entity-type":"item","numeric-id":802864,"id":"Q802864"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ebfc4e4322467180d128e113db763049e44afca2","datavalue":{"value":{"amount":"+0.7715137004852295","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":"Q789903$4D89B4E7-59D0-4387-9E8A-3517CE81FFB8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"313ec6d353f9e19d09f4de5b8b304ce81b5d52ab","datavalue":{"value":{"entity-type":"item","numeric-id":4732091,"id":"Q4732091"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e8df2e84b5ab2f0f85d55a56631835e5394e0881","datavalue":{"value":{"amount":"+0.7592841386795044","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":"Q789903$F17ABF18-B3E0-4486-987A-C26169DC2ABE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2956de18d395888f15c5656b5934a5b57f12696f","datavalue":{"value":{"entity-type":"item","numeric-id":2753934,"id":"Q2753934"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e5d5ba8e60658d267e8755e0f96ceff88dfcb308","datavalue":{"value":{"amount":"+0.7576809525489807","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":"Q789903$6E7870FD-DF1D-4284-8E79-3B1DC7B21FD4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a718b0ed5eae92b87e0c8980e58abc6d5ceb1faa","datavalue":{"value":{"entity-type":"item","numeric-id":4028872,"id":"Q4028872"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f967bb38cc731305c4ee3cad5eef476cc7a167b2","datavalue":{"value":{"amount":"+0.7574228644371033","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":"Q789903$83F3E639-1284-4218-8D3F-B28C19258C25","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:789903","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:789903"}}}}}