{"entities":{"Q1176318":{"pageid":1187067,"ns":120,"title":"Item:Q1176318","lastrevid":66434952,"modified":"2026-04-12T10:03:22Z","type":"item","id":"Q1176318","labels":{"en":{"language":"en","value":"Euclidean minimum spanning trees and bichromatic closest pairs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 14025"}},"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":"Q1176318$C0AF3626-5144-45CE-8190-0156DF9D5936","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"ef80cb5c8e66b747538e268919a72a2ce0f5c47f","datavalue":{"value":{"text":"Euclidean minimum spanning trees and bichromatic closest pairs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1176318$17A991D4-8B52-4F25-9B74-B55B7802A314","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"69ab704f007dc2a24bdb8df9429369584efef021","datavalue":{"value":"0753.68089","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1176318$B6470E86-DBE3-42DD-8CA3-8F1239BE7E57","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"5a7a461296a56c28785534f2a3bbf8a483b42b6c","datavalue":{"value":"10.1007/BF02574698","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1176318$6CB37195-6E7D-464C-84D0-DEA07E7BD4D7","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"677085c9ad30c4ba084dcc57c056b00b053188fc","datavalue":{"value":{"entity-type":"item","numeric-id":359871,"id":"Q359871"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1176318$43ECFA91-31EA-4788-A8BA-806E5741D0E3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"fe51ab34fca76d52c385a1ca93b7dc29b1c6d1a2","datavalue":{"value":{"entity-type":"item","numeric-id":1175645,"id":"Q1175645"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1176318$8B068459-5993-4D56-8EA7-AD385C062735","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":"Q1176318$1F9DDFC4-07B7-43A0-BF71-CA8E86D9FA47","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":"Q1176318$EC34A58A-17D1-4EE0-B40E-E34FA8F371BD","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":"Q1176318$15EB7C50-D5C2-4376-A83D-C6689CFB9AD0","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"d3f790682a6be4cc1f3210e15eebe1d6cc5ffbc2","datavalue":{"value":{"time":"+1992-06-25T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1176318$8B572036-D97E-4C47-A03E-C6DB435FECAB","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"4f6d702d995a28ffe0dfa5550d1c6d141fba17c9","datavalue":{"value":"https://eudml.org/doc/131167","type":"string"},"datatype":"url"},"type":"statement","id":"Q1176318$E8518C44-E87F-4A2E-93D8-CDCC17D65D01","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"be1966e25893847e4be02fb32854d4b79a403f46","datavalue":{"value":"The important problem of the efficient computation of Euclidean minimum spanning trees on \\(N\\) points in a fixed dimension space \\(E^ d\\) is considered. The authors develop \\(O(T_ d(N,N)\\log^ d N)\\) algorithm, \\(T_ d(n,m)\\) is the time needed for the computation of bichromatic closest pair of \\(n\\) blue and \\(m\\) red points in \\(E^ d\\).   Furthermore for \\(d=3\\) a fast randomized \\(O(N^{4/3}\\log^{4/3} N)\\) algorithm is described.   In my opinion the results, the analysis and the randomization technique are new and turn to be an essential tool for researches in computational geometry.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1176318$905FB2F8-BB34-4BB4-A342-4509BB6E4DA8","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"159426a5937e62cfbbcc198dd4848ab52d6e715e","datavalue":{"value":"68U05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1176318$2D58DD47-F466-4B07-9FBB-761127229AC8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1176318$D8CA2912-9850-41B8-994A-F86F1788D08A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"1de3565cfd3393000dd87ca545f95ff84d4c1446","datavalue":{"value":"68W10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1176318$5DE0BD3B-0451-43AE-BDAC-321646CEEEB1","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"ba790963519160ede0afc0bb063ea0aae7be6b17","datavalue":{"value":"14025","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1176318$9F410A8A-BEE4-4BF8-8AAE-B750EA28A77B","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"930816699e323987bf987f4de63664e42a9aab61","datavalue":{"value":"minimum spanning trees","type":"string"},"datatype":"string"},"type":"statement","id":"Q1176318$64362348-E7E5-4432-8555-DDF664FE2310","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d83092d4e8374e68f7077e7129b6dc82d63e58c2","datavalue":{"value":"bichromatic closest pair","type":"string"},"datatype":"string"},"type":"statement","id":"Q1176318$0A1F531A-7260-429C-B64B-4DFC09D75496","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"f536d576a7a86f81f786c7b361e2d5fc65a77932","datavalue":{"value":"Q54310199","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1176318$06631FE6-B32E-4D94-A877-739D7086413B","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"532bbaac3e370e50bd6ddecca89db5cad8ecea04","datavalue":{"value":{"entity-type":"item","numeric-id":1071506,"id":"Q1071506"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1176318$D8859A04-D6CE-48E9-92CC-D2517215EC84","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":"Q1176318$EA776B4D-3058-4757-96FC-4AD2335812FB","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"fb3ad06a850d903db617d4e20735c6d9d7e426c2","datavalue":{"value":{"entity-type":"item","numeric-id":1176318,"id":"Q1176318"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1176318$925D9F03-F841-4BB2-9B66-25050C4537CE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9aa91af4da23cedab6d65a9374c2c8969f96ef94","datavalue":{"value":{"entity-type":"item","numeric-id":3694706,"id":"Q3694706"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1176318$3640BDB4-1FDD-45A2-ADE7-E019F7BD9F0D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ec8b4d9c8ab43c964ebd317432f831e9e03ea515","datavalue":{"value":{"entity-type":"item","numeric-id":917017,"id":"Q917017"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1176318$9E66D0E4-B0C5-47D6-9B56-C0673831909E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"39501951ef662c90673b58c7b95b5797b92c1527","datavalue":{"value":{"entity-type":"item","numeric-id":3796754,"id":"Q3796754"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1176318$2CF167DA-14AB-4C4B-AE54-152E5A9E84A2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8853722611c41579d02ebd114c164fbf2e1b547d","datavalue":{"value":{"entity-type":"item","numeric-id":1823685,"id":"Q1823685"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1176318$E798C110-7B9A-4595-A283-CDFAB30AAE1A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9b1648e5adbae15097edfd823c49afa2b902a708","datavalue":{"value":{"entity-type":"item","numeric-id":1823854,"id":"Q1823854"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1176318$C4B71FED-614D-415D-83D2-EA4901C30C33","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":"Q1176318$9F56AD78-548D-49B3-BDBB-75D966E93493","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e29b8e47936578f5cad24b50941e85f6a32ad9da","datavalue":{"value":{"entity-type":"item","numeric-id":3738618,"id":"Q3738618"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1176318$B43C1ACF-E11E-4265-A9F8-7C01108DD189","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":"Q1176318$EE1026AC-9111-4D8D-85BB-3E0AC951B7BE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d8823c3d1f64066333ba239bc8c0398a943e7bd3","datavalue":{"value":{"entity-type":"item","numeric-id":4028870,"id":"Q4028870"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1176318$117607CF-FD50-4F04-AF41-59BA211B71C2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a49d6af7b2df96ccb57b811f981edcbee6fa50fc","datavalue":{"value":{"entity-type":"item","numeric-id":3954830,"id":"Q3954830"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1176318$A77BA3B6-F824-4A39-8625-0D748C6B7C7A","rank":"normal"}],"P1635":[{"mainsnak":{"snaktype":"value","property":"P1635","hash":"6b08a65e35d9da6514f9dcbf909edcdf647fbe1e","datavalue":{"value":"journals/dcg/AgarwalES91","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1176318$EE5DB6EA-62D8-4E85-99F4-7C20DDA292C0","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a472292056cbbc438d1ab8b1a621c8a666d739ab","datavalue":{"value":{"entity-type":"item","numeric-id":4037411,"id":"Q4037411"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fcce957881b03dabc4ac1487d22cfa9e530d3d2c","datavalue":{"value":{"amount":"+0.8553951978683472","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":"Q1176318$013D454B-1AB5-43AF-9563-371220FBAA58","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0ff63212e932bbc5449f78758ab5785f99fe5c06","datavalue":{"value":{"entity-type":"item","numeric-id":3798263,"id":"Q3798263"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"668fd9e43b4cbdf38effe45f6cb3d07fd6540f20","datavalue":{"value":{"amount":"+0.8495543003082275","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":"Q1176318$E804AD2F-500A-447C-A162-8A1A9F78DF81","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"795845f37e87974db5849a097267e5eab8ec082f","datavalue":{"value":{"entity-type":"item","numeric-id":911288,"id":"Q911288"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ec889595e24589d2a1f0d6c1edae1ec7cf2d4080","datavalue":{"value":{"amount":"+0.8494890928268433","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":"Q1176318$0E91C8D5-7632-42E3-BAB2-9BA813A2C638","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"91820f9aa5dde68961b05d0fe61c262b1fb7d646","datavalue":{"value":{"entity-type":"item","numeric-id":1194310,"id":"Q1194310"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5e94e5ee4e15cfdf534400e0696be769a611a5c9","datavalue":{"value":{"amount":"+0.8482202291488647","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":"Q1176318$EB062748-935B-48E0-96B1-29D0C35E681A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6d54347935cb8a0c3bde14e3b7f7ac2038227c6d","datavalue":{"value":{"entity-type":"item","numeric-id":4948733,"id":"Q4948733"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"61cb68979980d0143a57ba298585fc22461577f9","datavalue":{"value":{"amount":"+0.8460497260093689","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":"Q1176318$399A38D5-0948-40BF-96A0-D316C4075EBE","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Euclidean minimum spanning trees and bichromatic closest pairs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Euclidean_minimum_spanning_trees_and_bichromatic_closest_pairs"}}}}}