{"entities":{"Q706725":{"pageid":708574,"ns":120,"title":"Item:Q706725","lastrevid":63776187,"modified":"2026-04-11T15:28:18Z","type":"item","id":"Q706725","labels":{"en":{"language":"en","value":"Optimal spanners for axis-aligned rectangles"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 2132544"}},"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":"Q706725$CDB6BA6D-7F31-4956-8D4E-6AFAAAE79208","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"e7e2b5836830a0757b76ed648f8ec5b4ce5114d5","datavalue":{"value":{"text":"Optimal spanners for axis-aligned rectangles","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q706725$2CCBD71E-DFE6-4810-8140-724FE2082457","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"69b99a538b92a28ab432aa7bdae5e7cabb3d6a9e","datavalue":{"value":"1066.65025","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q706725$37BE864C-BBCB-4D8E-8A75-F526789270CC","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"ca0f809e75b605da89222285942806748678a6ab","datavalue":{"value":{"entity-type":"item","numeric-id":390166,"id":"Q390166"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q706725$7C2B64A4-9DCC-422D-A0CB-704EE11E8101","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"0dd41e0c9fd856e61a9a7227322992849270ab58","datavalue":{"value":{"entity-type":"item","numeric-id":293305,"id":"Q293305"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q706725$C8E2CC20-8D1A-4059-9AB1-4C9813239CA6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"857bf70e7d30bebc99244cb54d69e95a358f4fc1","datavalue":{"value":{"entity-type":"item","numeric-id":202561,"id":"Q202561"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q706725$E37BD702-9261-40AB-8C8C-5D7DB8FFE7D4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"83381eec9b184d4928dbc1724082cb2e43634626","datavalue":{"value":{"entity-type":"item","numeric-id":334943,"id":"Q334943"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q706725$AA8C0669-2668-4B48-AC31-53B4DCF16067","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"f238d7848d0d2745ced3187f54790200083b50d3","datavalue":{"value":{"entity-type":"item","numeric-id":802872,"id":"Q802872"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q706725$AE2A6FBF-8333-47A3-BD80-A3FD1C9D0915","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":"Q706725$AD4994F7-095C-4DA0-8F97-E95E457639EA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"2dbac174e7bb882624e2642be18b7dd92f382daa","datavalue":{"value":{"entity-type":"item","numeric-id":1776900,"id":"Q1776900"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q706725$06DD53EC-8700-4EED-B6AC-FA74FE759E41","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":"Q706725$5E1DFEF1-2D3E-42C5-A75F-D62936FA0066","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"0bb430d98445fad0c07a301b258c507df3dbc1f9","datavalue":{"value":{"time":"+2005-02-09T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q706725$A4F79F26-7AA1-4B52-ABAC-906A9F4003FE","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"952e23ba3de105ab66b56274ab16757fe095f449","datavalue":{"value":"The authors propose an approach to the problem of finding the connection segments that minimize the dilatation in a bridge graph, i.e. the graph which describes which pairs of rectangles from the given non-intersection rectangles are to be connected. It is proved that the graph contains cycles, then the problem cannot be solved in polynomial time, but if the graph is a path or a tree, then the problem has polynomial complexity. It is also proved that in the case of a set of rectangles sorted vertically along a path, an estimate of the problem solution can be found in linear time.","type":"string"},"datatype":"string"},"type":"statement","id":"Q706725$BCC49650-5193-49BE-A47E-37CBA26DB6F5","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"2f9e16b52bc8c390b9fea0fb31de1975133dd070","datavalue":{"value":{"entity-type":"item","numeric-id":455938,"id":"Q455938"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q706725$29339B97-666E-4F2D-8BF6-80E5F410AA9A","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"2ce72165d993b0b8ed97728d731d2db2473b9554","datavalue":{"value":"65D18","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q706725$AE3B6265-F3EB-4BCF-8B4B-9459908BBE3A","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"97b1d4f0c17c80e5040350a2065ddf1d6cb83ff2","datavalue":{"value":"2132544","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q706725$4C4925F9-EF09-42B7-A07D-1571E49A3E09","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"db5ac41838f32d14f7818ae2a91b743831754dfe","datavalue":{"value":"optimal spanners","type":"string"},"datatype":"string"},"type":"statement","id":"Q706725$353911BC-D31E-4D31-ABF3-3E6EA8BE9163","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d3d96e3d74138447af545d0cb2d3866006bca24c","datavalue":{"value":"rectangles","type":"string"},"datatype":"string"},"type":"statement","id":"Q706725$5589909C-379E-4634-82A6-972531756606","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ee54989b2d0d0e43b36a5ebe041948fdd7c84a7e","datavalue":{"value":"minimized dilatation","type":"string"},"datatype":"string"},"type":"statement","id":"Q706725$6E8A9740-B4CF-484F-A02B-C678A09600A3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f4661a1cc7b7803a27ee6edef81ea621577535ca","datavalue":{"value":"Geometric spanners","type":"string"},"datatype":"string"},"type":"statement","id":"Q706725$B9C22EBF-AE94-4F1C-826B-C9EC5DB2687D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"415b20f999ad7583d05c3de5df61919242bcdc8e","datavalue":{"value":"Dilation optimization","type":"string"},"datatype":"string"},"type":"statement","id":"Q706725$4E3AA42E-5710-41F7-B1A0-514825E8D8DC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"744b34dd338f141368ec35b1caed0a6238f8f50c","datavalue":{"value":"Isothetic rectangles","type":"string"},"datatype":"string"},"type":"statement","id":"Q706725$5B86D478-40A4-4905-AC8F-48CC7B121B5A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5fe03eaa6e593c6aa6fd136c2e0018da936cfe6b","datavalue":{"value":"Manhattan distance","type":"string"},"datatype":"string"},"type":"statement","id":"Q706725$F75F45BE-F90C-481D-A66C-5362FA4ABE94","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"10b37adb54f4933c62b67ac706b04cd4c2c55783","datavalue":{"value":"bridge graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q706725$6ACEAB9C-39CC-426D-B460-C373B83BB597","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"267b394071cf1b5b643cd515aabcdbcae8c08f98","datavalue":{"value":"polynomial complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q706725$56D756BC-CF40-499F-BD3F-25C01E196D7E","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":"Q706725$2ACDD90B-EEE2-4AD9-ABDC-5C918E9EB685","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"747695b2d466b803a0dfe2b8a0362810d81eaf5b","datavalue":{"value":"https://doi.org/10.1016/j.comgeo.2004.09.001","type":"string"},"datatype":"url"},"type":"statement","id":"Q706725$832E9A72-F185-4A39-9FCF-F7CF34C34465","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"47e26d29c4d4cd5f4946269b74a89e4031ca4cfd","datavalue":{"value":"W2131984062","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q706725$0668CB39-04C4-4165-838F-3E187C72F235","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"25476c5dee233b3e452617b2a2a65c9d9feb32b8","datavalue":{"value":{"entity-type":"item","numeric-id":3990609,"id":"Q3990609"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q706725$2E9543D0-BE2B-40C5-980B-EB565A0094A8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d0d029af071a8946ee1662887e0e0b0ab0a7ae3b","datavalue":{"value":{"entity-type":"item","numeric-id":4344150,"id":"Q4344150"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q706725$7BE2B428-78B7-4839-B227-18FC1CB26481","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1a7d12ad715ea384e4f5dfa32c3b1f65fa44d396","datavalue":{"value":{"entity-type":"item","numeric-id":1823959,"id":"Q1823959"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q706725$05D6346E-869C-48E6-AAE2-3E1E144DA343","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"60823dfccc4e3f3a4b3977f2a4d0dcb880104c9c","datavalue":{"value":{"entity-type":"item","numeric-id":4945509,"id":"Q4945509"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q706725$4E62917E-7F34-4E87-ABAA-D26A627DC722","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"836ad2a04f82225da478ca9f694f5cd99360b315","datavalue":{"value":{"entity-type":"item","numeric-id":4198056,"id":"Q4198056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q706725$258E76DE-D6FD-4D33-AFEE-A3A3268B135F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a0b86da6901907b4b60c4d755cbdefb3d87af7f5","datavalue":{"value":{"entity-type":"item","numeric-id":761967,"id":"Q761967"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q706725$A1D765A4-43E0-4D89-9D7F-B5657FAB1C1E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6e424f1c4ff7c6f161b20d25abc72aff42c0b5cc","datavalue":{"value":{"entity-type":"item","numeric-id":3763585,"id":"Q3763585"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q706725$9212846C-8F2F-4BF9-9FB9-1B9C13544710","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bd94578b97c83ef7077e73a3f78c579ae10dd88b","datavalue":{"value":{"entity-type":"item","numeric-id":3826599,"id":"Q3826599"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q706725$8C7A6B60-9504-493C-821B-1B9D552C4569","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"85db1048a8bda2c53a7443e7a00f73f05b0cfccc","datavalue":{"value":"10.1016/J.COMGEO.2004.09.001","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q706725$A52C5855-7433-4560-9F7D-6E42F1D7730C","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"85d247bc2aa4a656054522d7e0bfb7321a0e8cee","datavalue":{"value":{"entity-type":"item","numeric-id":3511351,"id":"Q3511351"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ac22cff0a4ae33c900225c01c73928301ada54e0","datavalue":{"value":{"amount":"+0.7966502904891968","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":"Q706725$58159A26-9F6B-470C-B475-C1E47A59DB12","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cc37b493115cdc279ba187ad8d507a4f70e49cd4","datavalue":{"value":{"entity-type":"item","numeric-id":3196394,"id":"Q3196394"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4fcc4ba6d66e1be10851a51c5bcead3d7c8ae6a4","datavalue":{"value":{"amount":"+0.7946799993515015","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":"Q706725$3BD1E04D-FEED-4E1E-8B8C-97FD68B6C825","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e85f212cebe6b21ea946264d747933e105e3b70f","datavalue":{"value":{"entity-type":"item","numeric-id":3595495,"id":"Q3595495"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3d8735acef111b0b3cb64ef5b68cd6f3ade14498","datavalue":{"value":{"amount":"+0.786712110042572","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":"Q706725$DD4A6243-67AC-44F9-AA38-D6AB8628BB2E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"98d6d35fa2f2557a24e677266804bffeec977936","datavalue":{"value":{"entity-type":"item","numeric-id":3562852,"id":"Q3562852"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"39d0f9f3f9ef24796f4c918eb323cf91ad84dafc","datavalue":{"value":{"amount":"+0.7824743986129761","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":"Q706725$EDEFDFD6-F4DF-4A81-95C4-81753E7E8795","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"425b3d4996f555d9f12e3efd5af2f70404df460c","datavalue":{"value":{"entity-type":"item","numeric-id":945943,"id":"Q945943"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1fadc3aef3ab51c618d9b473c1699e1661cfc9ca","datavalue":{"value":{"amount":"+0.7803975939750671","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":"Q706725$14EE64E8-B48F-4084-A6D5-D5F6FBD8B967","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Optimal spanners for axis-aligned rectangles","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Optimal_spanners_for_axis-aligned_rectangles"}}}}}