{"entities":{"Q1263993":{"pageid":1274743,"ns":120,"title":"Item:Q1263993","lastrevid":68331930,"modified":"2026-04-12T22:59:27Z","type":"item","id":"Q1263993","labels":{"en":{"language":"en","value":"Heuristics for optimum binary search trees and minimum weight triangulation problems"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4128409"}},"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":"Q1263993$4DBA43B0-CA38-4852-B466-30456A17D8F7","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"ece760d49bbcf57d0f36e0bf573b25dceac5d048","datavalue":{"value":{"text":"Heuristics for optimum binary search trees and minimum weight triangulation problems","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1263993$272CDA6F-7045-4532-893C-B84790277821","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"82fd8b324c86e27aee3d6cfdf9f055990c8d1acb","datavalue":{"value":"0688.68063","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1263993$4173CC33-DBDD-43DF-9028-40B56A8C4D82","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"14a604a8e5001840077b395c28d6457f53d492f1","datavalue":{"value":"10.1016/0304-3975(89)90134-5","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1263993$6FA7AB46-53AD-4796-8C4C-C78270AFB331","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"d0dc835d004d9da5bffbf23ad19f48702adc4590","datavalue":{"value":{"entity-type":"item","numeric-id":582112,"id":"Q582112"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1263993$29D463A9-739C-4DA5-A945-B546A8BA0E00","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"00dfebb11dde3a8ec3e20741cb39008a3351335c","datavalue":{"value":{"entity-type":"item","numeric-id":293198,"id":"Q293198"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1263993$45797772-30A4-47E0-AD05-F32604E178C9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"ca02099175697a4b54d6c3e10f20112dbf6ee98b","datavalue":{"value":{"entity-type":"item","numeric-id":170449,"id":"Q170449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1263993$CA2A4FA8-06F7-4172-A092-731F45E8A6D9","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f3c424cd94a60f9664f9fb69cc6027e75cc7ff3f","datavalue":{"value":{"entity-type":"item","numeric-id":123643,"id":"Q123643"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1263993$123E7446-8EFB-46AE-80B2-A57BEB7DA066","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"7211ad5ca16eb0d22cd0051fff3d0f3af254ceb6","datavalue":{"value":{"time":"+1989-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":"Q1263993$32D8CF7E-2677-4C37-975E-C2BCBB8CECD5","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"1d5cfa8238e601284c3ea52b44880701da480d2b","datavalue":{"value":"The article addresses the following problem: Construct optimum binary search trees, given a set of keys \\(K_ 1<K_ 2<...<K_ n\\) and the access probabilities, namely the special case with zero-key access probabilities (it means zero probability \\(K_ i\\) is the search argument and non zero probability the search argument lies in the interval \\((K_ i,K_{i+1})).\\)    First, the authors proved one-to-one correspondence between zero-key access probability optimum binary search trees and the minimum weight triangulation of a special type of polygon (in fact they prove more general result concerning correspondence between (m-1)-way search trees and partition of certain type of polygons into m-gons). Then they show heuristics for triangulation of polygons of this type and translate them into corresponding ones for optimum binary search trees. Going other way, a lower bound on the approximation factor of the greedy heuristic for binary search trees also proved in the paper can be translated into a corresponding lower bound on the approximation factor of the greedy triangulation for corresponding polygons.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1263993$E4ECCFFD-F40F-413D-A09C-B3D1E7BE291B","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"3f97694d44af155a68434cb72eabc6a4d5dd5227","datavalue":{"value":"68P10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1263993$B68A3A99-470D-4A11-9551-5BA7F8A083AC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"9ed1e3c6cced595a05b8ae19055521b22405b78a","datavalue":{"value":"68W99","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1263993$DAED67A3-0141-4F2E-97CE-83A4FDC7AEB8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"ddd8cb1932c6bc41681458db5f685a2a286fde55","datavalue":{"value":"52Bxx","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1263993$09DA2DF6-42B8-41E4-94B1-F883DA7CE6F9","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"5a2641df7edb56e3bfd1a1cf4206e6fc7835c9d0","datavalue":{"value":"4128409","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1263993$63C37386-7872-4B5A-B38B-FF1D9D1C0A5F","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"698da498debf95b20521af5ea7a8edf5a609dd8a","datavalue":{"value":"optimum binary search trees","type":"string"},"datatype":"string"},"type":"statement","id":"Q1263993$D07D1BBC-7A19-4270-8FB3-58F6401F7373","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2e984adb86ecfd745f8c2b2f4daabbab1477ce54","datavalue":{"value":"minimum length","type":"string"},"datatype":"string"},"type":"statement","id":"Q1263993$2F874054-FCA0-4214-9075-3BA027870F09","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f8c7ca0297a9e089061263adbd9465793cf35c29","datavalue":{"value":"partition of polygons","type":"string"},"datatype":"string"},"type":"statement","id":"Q1263993$8EB3360A-17F6-4F37-A1A3-2425FB516716","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cda0beed555938d8dc24f2325c7f1a7d775e838a","datavalue":{"value":"heuristics for triangulation of polygons","type":"string"},"datatype":"string"},"type":"statement","id":"Q1263993$B6660597-FF97-4248-8D9B-E5B1581C22E4","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"4418b7d4f2a0250db5c25bb23e561efd56a43eb7","datavalue":{"value":{"entity-type":"item","numeric-id":587571,"id":"Q587571"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1263993$478A8609-BC98-464D-8C3E-C9B74BD74745","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"5d966c2924f73800342268f160c141e905bb7c32","datavalue":{"value":"Q62037522","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1263993$C6F7FCB0-083C-45C1-A135-5B60BD6801B5","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":"Q1263993$5673D114-2EEB-4A02-A6B0-ACC24652FD30","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"fa160e7646ac8d30d7df371a3b0923703307ed5a","datavalue":{"value":"https://doi.org/10.1016/0304-3975(89)90134-5","type":"string"},"datatype":"url"},"type":"statement","id":"Q1263993$5E831AE7-3F27-48F4-BA6A-218DC51D9FFD","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"4153f76c4c6f3ff6d1eedd5c75a13af9205afac6","datavalue":{"value":"W2074341520","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1263993$230F8718-8B32-474C-8391-4F2C13A41D60","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"951a61387e0baff6c4ab4135dbba5836ecae6bc0","datavalue":{"value":{"entity-type":"item","numeric-id":4142686,"id":"Q4142686"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1263993$16BBBA25-C87D-42F2-AA64-234C4CD71CA3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"91d0f5ab233e414c684abbb389e5f82d2ca7af57","datavalue":{"value":{"entity-type":"item","numeric-id":3911413,"id":"Q3911413"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1263993$C83A1F35-F39F-47A1-9225-27EE45FDE59A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f3f2b8b8a05c5e5e1a73bff13e01a1b382c27155","datavalue":{"value":{"entity-type":"item","numeric-id":5636753,"id":"Q5636753"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1263993$D4699CDC-C15E-418B-BCDA-44F32DBF9D7A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5b7ee5780baed1d7856c99389fada17672a0a4e3","datavalue":{"value":{"entity-type":"item","numeric-id":3898497,"id":"Q3898497"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1263993$0F9248EB-5502-4629-9245-0435A6A2F47C","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":"Q1263993$78BBEC59-DB25-4CC6-8BC9-50AAE8EF8332","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4aa19aeccb345d1060789029c98473152e5ba63f","datavalue":{"value":{"entity-type":"item","numeric-id":1098295,"id":"Q1098295"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1263993$4C7A18CA-578C-445E-AAC3-E5DABF418FA3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ab9002c6ee03c89bc48bc9e3b89404864edba99f","datavalue":{"value":{"entity-type":"item","numeric-id":1250433,"id":"Q1250433"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1263993$340FB3A9-AB22-4E75-9E6C-F32E1971B380","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9387bbd38b0874a230355988a020913f3259fce1","datavalue":{"value":{"entity-type":"item","numeric-id":3219751,"id":"Q3219751"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1263993$5192782E-AA98-42C5-AB3B-090732A108EA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"694910451200ab7067ebbccacf142af3ac2a2369","datavalue":{"value":{"entity-type":"item","numeric-id":3992847,"id":"Q3992847"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1263993$385057BB-07B1-4F10-9EE4-FE77AF0AFEB3","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"83b49a0e3d5f186f2ca0749a345a84376ec6e7d3","datavalue":{"value":{"entity-type":"item","numeric-id":3783595,"id":"Q3783595"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"653cdc3f1372328126a232e38fbe90b61cd2184a","datavalue":{"value":{"amount":"+0.9117202162742616","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":"Q1263993$8F96B909-F877-4609-B75A-D9B09DA5EBB8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"668e0f4becd6fbbfb0f26651d57d1d55460fa705","datavalue":{"value":{"entity-type":"item","numeric-id":5906917,"id":"Q5906917"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e9935811ea70f996aad9d7957caf3bbcb712bf85","datavalue":{"value":{"amount":"+0.8231750130653381","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":"Q1263993$311F81C6-616E-47BF-A82C-9A1B7E8315BB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"657854cba877e7ed3032d223bf35aae944abfc16","datavalue":{"value":{"entity-type":"item","numeric-id":2366072,"id":"Q2366072"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a799b37e22155e8aabe1b66368823f25fc578ee7","datavalue":{"value":{"amount":"+0.7801011204719543","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":"Q1263993$5AC94AD5-2EC2-4423-9214-9CA301506FB5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"778a8ffb86f6d3a7e132fee72775276809c1beea","datavalue":{"value":{"entity-type":"item","numeric-id":4437486,"id":"Q4437486"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a732d11f0ad71640a36e1e2e5069716cca3ba262","datavalue":{"value":{"amount":"+0.7634971737861633","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":"Q1263993$A78A50BD-F5FC-469D-BA8B-A8B59C72325E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d7eb631ba49e758368781402739362f3f3ce087e","datavalue":{"value":{"entity-type":"item","numeric-id":4512247,"id":"Q4512247"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"dfa90d5a06c386732c0d37cfdd081515730525dc","datavalue":{"value":{"amount":"+0.761651873588562","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":"Q1263993$85DD9B49-F0AD-4221-B054-EB48F0A1B67C","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Heuristics for optimum binary search trees and minimum weight triangulation problems","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Heuristics_for_optimum_binary_search_trees_and_minimum_weight_triangulation_problems"}}}}}