{"entities":{"Q904112":{"pageid":905960,"ns":120,"title":"Item:Q904112","lastrevid":65225460,"modified":"2026-04-12T01:09:31Z","type":"item","id":"Q904112","labels":{"en":{"language":"en","value":"Approximating the bottleneck plane perfect matching of a point set"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6531083"}},"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":"Q904112$3B943DC2-1B3D-4DCD-A1DA-DC219B0FD0DA","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"0e9801d2336b191e886084428e48d3f5ae43fabb","datavalue":{"value":{"text":"Approximating the bottleneck plane perfect matching of a point set","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q904112$6859CC0F-8AEA-45A8-9D57-10F61E3696E5","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"18bb284d65ed35bf5ef804554e7e0e00ab5ec619","datavalue":{"value":"1332.65029","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q904112$6542EF59-B0B4-4B5F-83A8-C5E089F5B80B","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"ca88e1c4a6c56c9b0306810f7f223a70f6fb7e76","datavalue":{"value":{"entity-type":"item","numeric-id":390161,"id":"Q390161"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q904112$1CFD6E7C-9B16-4FD3-AC53-605483842A68","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"cd43af1473526fde659c81b01066ab1feaab947d","datavalue":{"value":{"entity-type":"item","numeric-id":390151,"id":"Q390151"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q904112$59AB2127-F4D9-483C-9A01-64DA022B2B03","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"a266d729c395220c0c1ce9741b7a6ad65b6115d8","datavalue":{"value":{"entity-type":"item","numeric-id":390162,"id":"Q390162"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q904112$26FB638E-CA70-4EB0-8C12-575B93136A9A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"38d792d47a26d779a5d4ebfefe81eefffc2d9963","datavalue":{"value":{"entity-type":"item","numeric-id":170448,"id":"Q170448"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q904112$4B919ACA-32B1-47EA-8650-B39A065B9BD2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"ad5167b666b6ff8ea720dcdbc03cbe41b9c51f06","datavalue":{"value":{"entity-type":"item","numeric-id":582044,"id":"Q582044"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q904112$0DF674A3-7C6A-4E8E-8FFE-C2D611C97E72","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"285beb29e5e30a7ba8792191178d7f52682884ef","datavalue":{"value":{"entity-type":"item","numeric-id":175378,"id":"Q175378"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q904112$55F9FD3E-0FDE-46F7-8963-FF8348D80D6E","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"8c2e70900021c1099dc2c52f195923a82bcef5cb","datavalue":{"value":{"time":"+2016-01-15T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q904112$E435FD1A-512C-4CAB-BDA7-343C079C0D00","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"2431242a6bec42a27a249f858c59cba63b05a45e","datavalue":{"value":"https://arxiv.org/abs/1311.5197","type":"string"},"datatype":"url"},"type":"statement","id":"Q904112$86242C93-2CA1-4BD6-A60E-20AEA56F4043","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"bd9d83629749c9a0603cc436758dfddceb9dcefc","datavalue":{"value":"\\textit{A. K. Abu-Affash} et al. [ibid. 47, No. 3, Part A, 447--457 (2014; Zbl 1281.65025)] showed that the bottleneck plane perfect matching problem is NP-hard and presented an algorithm that computes a plane perfect matching whose edges have length at most \\(2\\sqrt {10}\\) times the bottleneck. The present authors present an algorithm which computes a plane matching of size \\(n/6\\) in unit disk graphs (UDG) and observe that the problem of showing if this algorithm terminates in polynomial number of steps or not, is still open. Presenting a \\(2/5\\)-approximation algorithm for computing a maximum matching in UDG, and by extending it, the authors show how one can compute a bottleneck plane matching of size \\(n/5\\) with edges of optimum-length.","type":"string"},"datatype":"string"},"type":"statement","id":"Q904112$87D4C5C9-E7EB-4CC2-84CE-CD2558A9B65D","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"956419f6fd71b8dac027f33d0ad5be15c64817eb","datavalue":{"value":{"entity-type":"item","numeric-id":182524,"id":"Q182524"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q904112$E9ED80FF-B938-44D8-A6A2-7E2AE8359B53","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"2ce72165d993b0b8ed97728d731d2db2473b9554","datavalue":{"value":"65D18","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q904112$2208E5EC-0AB2-4443-8BAE-112466A6E0FB","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"39b431d51a54d8e203353a6936a9c8d6062a530e","datavalue":{"value":"6531083","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q904112$24D8B07A-0349-4B50-BC71-10DC37797DBE","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e2ef78ffb9a021351bdd7fbe626831153dde2186","datavalue":{"value":"plane matching","type":"string"},"datatype":"string"},"type":"statement","id":"Q904112$37176499-33A9-4A3E-9C45-04271D6CA357","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1a5404ba22202a04365275df96c6c6c83638ac46","datavalue":{"value":"bottleneck matching","type":"string"},"datatype":"string"},"type":"statement","id":"Q904112$AADD0801-5768-4B74-A896-FECE4373F9D3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0cd2bad7f8171f3265bcc7063cb3c4ccf853f203","datavalue":{"value":"geometric graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q904112$72BBF6B5-1EB7-42E8-9C3F-F6F890442D59","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cfa4ce6cfbd5e618995529bd1343a4a7f34072a4","datavalue":{"value":"unit disk graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q904112$336C5E21-272D-4889-983C-FE5DA88FB966","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0de600cf8191fa1f423fd01c9a02b172072a7391","datavalue":{"value":"approximation algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q904112$3C348202-9EC5-413C-BF9B-957DA1CAD175","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8f12ea105addea4e52f9511695748975bd61a49c","datavalue":{"value":"NP-hard","type":"string"},"datatype":"string"},"type":"statement","id":"Q904112$73210F21-AB2F-40B1-AB9A-23BFEBC5DFDB","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":"Q904112$B5E9D706-D076-416C-BF1E-D38CBC8BB1FE","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"04a70ab0cd91a561709da08849d3d050f6069774","datavalue":{"value":"W1710148940","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q904112$CA7D23A7-7935-480A-B2C6-E25FD1480DA6","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"73f2ca6dff3cc58506ebb73c8c84ac9ee7f5d74b","datavalue":{"value":{"entity-type":"item","numeric-id":390164,"id":"Q390164"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q904112$609396E6-AE21-4AE4-BEE5-BACFFDA70A92","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ee4eeb5b27079da16287b507c3f4355500116a5b","datavalue":{"value":{"entity-type":"item","numeric-id":714905,"id":"Q714905"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q904112$D55DC1A4-8ACB-4C6C-BE7E-EA3E65836104","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a0f57de1982234370231b87d2b05eef81d14a01e","datavalue":{"value":{"entity-type":"item","numeric-id":2792796,"id":"Q2792796"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q904112$E7CDBA0E-F0EC-4166-841F-D912D6F383E8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e641daca65e11c6124b3221139f36b5d843545d7","datavalue":{"value":{"entity-type":"item","numeric-id":1194341,"id":"Q1194341"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q904112$114F7A54-DECA-4EEE-B4A8-8DCACAC31A7D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4241f8308d167565bbead4d0eec3525ac106e02b","datavalue":{"value":{"entity-type":"item","numeric-id":5452284,"id":"Q5452284"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q904112$F973508D-941D-49F7-AEEF-11FA27AB76B1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c39738cea79e11456d6583aec1786d79af209b23","datavalue":{"value":{"entity-type":"item","numeric-id":5341586,"id":"Q5341586"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q904112$8E871EFA-477E-4CD5-8029-68D047A0743A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d4aee9a148f4b7053c8439ae8a1a20d4f3d50c4a","datavalue":{"value":{"entity-type":"item","numeric-id":5946120,"id":"Q5946120"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q904112$C7452D4D-53C6-4AA2-B2B8-2B98B6EADDB0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3e6275a5f92e83007c178524ecfc8afd6a2b9ed9","datavalue":{"value":{"entity-type":"item","numeric-id":1607062,"id":"Q1607062"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q904112$95E475B0-E3BB-40CE-8858-CE84BB19773D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e579aa4704eaeaa9ad5064e4744c9d902a73e187","datavalue":{"value":{"entity-type":"item","numeric-id":3997942,"id":"Q3997942"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q904112$9F57129D-DCE9-46E7-AC11-E1E6C4847BF9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"82cbdc4a2ba4de52a71e9bb1596d2f0946f9ea51","datavalue":{"value":{"entity-type":"item","numeric-id":1199130,"id":"Q1199130"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q904112$3D30B95E-2CAE-4DD7-AF41-63D2E776E7B4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c866ca73aa353d78d83a6b61a814fbc2345d2702","datavalue":{"value":{"entity-type":"item","numeric-id":3034826,"id":"Q3034826"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q904112$634A99B8-9020-435B-B3AA-0B897BAF4D5E","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"25acd7c015019e989b372f60f8986d472e0018c2","datavalue":{"value":"10.1016/J.COMGEO.2015.06.005","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q904112$0EA3AABC-2AAF-4A4F-A745-D3A769431863","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d5260aee1911b5a95421844a5310d639725c9e12","datavalue":{"value":{"entity-type":"item","numeric-id":2912824,"id":"Q2912824"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"127fa2d4b88ac0a70d39c11df1746c8d3de8fb00","datavalue":{"value":{"amount":"+0.7991622090339661","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":"Q904112$1B5159E4-C854-48C9-A3C0-8D97455F2ECB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c9b1bb7ed570d2fc6e6afc56e7ca6719326cb8e5","datavalue":{"value":{"entity-type":"item","numeric-id":390164,"id":"Q390164"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d9a6fe8040af7f42e4456ac8288fd3c7d043153b","datavalue":{"value":{"amount":"+0.7976840734481812","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":"Q904112$0EBA1B64-550D-4143-A38F-059B3980C663","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"65b645abcfb84b8509aa7c3d310057a2e16ee131","datavalue":{"value":{"entity-type":"item","numeric-id":1194341,"id":"Q1194341"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1a857ba88fceffefe20be5e8f70a40e4df9ef0a1","datavalue":{"value":{"amount":"+0.7877976894378662","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":"Q904112$0393BEF8-D9BA-4604-A8FD-1C24B4839F55","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ee331887375f61442e7d0a7b045ada4df40bdbf7","datavalue":{"value":{"entity-type":"item","numeric-id":6487431,"id":"Q6487431"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2a168d9dee7bb757850d2b605b29186c9fda7623","datavalue":{"value":{"amount":"+0.7875710129737854","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":"Q904112$37E4CE2D-93CB-4A50-8728-8761BF590CD8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"adfc1066c5a584db473948840c6d501c1cb53c53","datavalue":{"value":{"entity-type":"item","numeric-id":4252363,"id":"Q4252363"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a8aab714366c76535d77b1fb217d358f693bef87","datavalue":{"value":{"amount":"+0.7810471057891846","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":"Q904112$D1E1E999-6FCA-4822-BA6F-CAB3392C6A66","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Approximating the bottleneck plane perfect matching of a point set","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Approximating_the_bottleneck_plane_perfect_matching_of_a_point_set"}}}}}