{"entities":{"Q758223":{"pageid":760072,"ns":120,"title":"Item:Q758223","lastrevid":64149147,"modified":"2026-04-11T17:57:58Z","type":"item","id":"Q758223","labels":{"en":{"language":"en","value":"An improved upper bound on the number of intersections between two rectangular paths"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4195228"}},"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":"Q758223$0F22EBE8-1BDC-40ED-839A-9B39463E32B1","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"34fee96960ad84d1448e4f749ba8dca181e8922f","datavalue":{"value":{"text":"An improved upper bound on the number of intersections between two rectangular paths","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q758223$F9788EAC-1B72-49FD-BF2D-3A99AB5E70D3","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"9e434e2f0e3ad8af03d9967e6c3a2e116208b0fa","datavalue":{"value":"0724.68093","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q758223$2AB2EBB3-0321-4918-B775-7B944E45CCCD","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"97c90e00eb9cc1817f6c6dfaae6153e348b4e895","datavalue":{"value":"10.1016/0020-0190(91)90146-9","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q758223$F4BAD9B2-B517-4A9B-9C71-B08C9E128EF6","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"714f64a86144878ee8df249e4d813e09af6c7d30","datavalue":{"value":{"entity-type":"item","numeric-id":758221,"id":"Q758221"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q758223$66066AE5-E378-42C5-AE87-34616D9E6603","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"4fb35263c91ce4a744a014633f26b848fed1a5c3","datavalue":{"value":{"entity-type":"item","numeric-id":758222,"id":"Q758222"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q758223$7440D635-0D64-4CDF-8E77-3A8EE9368BA6","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":"Q758223$B3B3D39E-AF8C-4383-B520-3E6319DE2304","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"391107ffc7a24346d69c573e292e4ff4587e3aaa","datavalue":{"value":{"time":"+1991-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":"Q758223$D1CD659A-69D9-4C16-861E-8B999966B48C","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"dbedbae4919ce21bc7e40d697ddcad568cf11191","datavalue":{"value":"Let I(P,Q) be the number of intersections between two rectangular paths P and Q. \\textit{K. Kant} [IEEE Trans. Comput. C-34, 1045-1049 (1985; Zbl 0572.68057)] shows that  \\[  I(P,Q)\\leq \\frac{10}{9}| P| | Q| +\\frac{4}{9}(| P| +| Q|).  \\]  Recently, Wang et al. improved the upper bound to  \\[  | P| | Q| +\\frac{1}{2}\\min \\{| P|,| Q| \\}+\\frac{1}{3}\\max \\{| P|,| Q| \\}  \\]  and conjecture that the bound cao be further sharpened to \\(| P| | Q| +2\\) for \\(2\\leq \\min \\{| P|,| Q| \\}.\\)    An upper bound on I(P,Q), where both P and Q restricted to be monotonic, is derived, the conjecture of \\textit{Y. L. Wang}, \\textit{R. C. T. Lee} and \\textit{J. S. Chang} [The number of intersections between two rectangular paths, IEEE Trans. Comput. 38, 1564-1571 (1989)] is validated.","type":"string"},"datatype":"string"},"type":"statement","id":"Q758223$7155665F-EF59-45D9-8144-3900F40146F9","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"159426a5937e62cfbbcc198dd4848ab52d6e715e","datavalue":{"value":"68U05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q758223$39137CEA-0A1F-45D9-95A2-6F14BBBD352F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q758223$60F6E13D-3297-42B7-928F-60DBAD788A68","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"efd2b8f985faf43becf0f0cf27b3e2bef2d2d26d","datavalue":{"value":"4195228","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q758223$A8EABBBC-76EE-4C55-BF83-722A8F781722","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"bdf2cfbc6e4ef9d6558d9f0ed6d4633eea496912","datavalue":{"value":"interference","type":"string"},"datatype":"string"},"type":"statement","id":"Q758223$D371E615-D9AD-45C4-B7E9-3131610FD9A2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"22bf57f5dd7fd116d34a1a789bd1bf0b6d51d6a1","datavalue":{"value":"VLSI layout","type":"string"},"datatype":"string"},"type":"statement","id":"Q758223$84D2ADF9-5514-4177-997C-DF99B0CB36DD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cbffb8ae14b4f37eab0c3aace9f763172d33b5b2","datavalue":{"value":"intersections","type":"string"},"datatype":"string"},"type":"statement","id":"Q758223$4677A7E1-DD4F-46CB-972B-09BB4C8E4283","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c9cca93ad47c3ac3e6187a2cc7c6a118a8ac31d1","datavalue":{"value":"rectangular paths","type":"string"},"datatype":"string"},"type":"statement","id":"Q758223$756DE338-5E2B-45D3-890F-9D33ACFC5359","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"817f91d754a6618dd027e0d851a1fc8b7cbc7134","datavalue":{"value":"upper bound","type":"string"},"datatype":"string"},"type":"statement","id":"Q758223$F9B2FE0D-2E95-4D4C-BA31-BF844B7397A1","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":"Q758223$CCC36119-488E-44B8-846B-3594DD05085D","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"2ae39198cc0afe9635f563896755d4f27620ec60","datavalue":{"value":"https://doi.org/10.1016/0020-0190(91)90146-9","type":"string"},"datatype":"url"},"type":"statement","id":"Q758223$0594CEC6-C44B-40A8-A65B-8CD5BDFDBDF4","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"97ebc6362729622611ac1d01fef8b393085b5b14","datavalue":{"value":"W2070379127","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q758223$D02A253B-9216-42FB-A4F7-BC95DDB0F1FC","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"90c10f3313dde19a9252305df9d45bc029891d9e","datavalue":{"value":{"entity-type":"item","numeric-id":3049855,"id":"Q3049855"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q758223$5D9662D2-82C8-4913-A025-18DF1047D9F6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c2b1b3f3f4950cb6507e070a529c071cf93d86be","datavalue":{"value":{"entity-type":"item","numeric-id":3893371,"id":"Q3893371"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q758223$42506476-F476-4993-8AE5-5BBBF0B0E722","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"abe380fcd9c0753c8833e479b183546872ee6936","datavalue":{"value":{"entity-type":"item","numeric-id":1821557,"id":"Q1821557"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q758223$BC1EC056-48A9-4FCB-AF66-62DA375CDC17","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"82272d99567c39611c61dfc428edf2015de85ae0","datavalue":{"value":{"entity-type":"item","numeric-id":3690239,"id":"Q3690239"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q758223$44475438-6AC8-4D10-826F-7C85EA754433","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a424f44a8dbc665539390a6f9c8785edbdbed5f3","datavalue":{"value":{"entity-type":"item","numeric-id":3953198,"id":"Q3953198"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q758223$259860D3-8D1B-48A5-A5D8-2E485B225D66","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"28d1d1cb66d27d2e53aba37392ad47b61e11f859","datavalue":{"value":{"entity-type":"item","numeric-id":3326832,"id":"Q3326832"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q758223$72995B79-A863-41C8-8593-08039CCDFCE6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a105fa598847a58dd40958aadd6735a838c8f98d","datavalue":{"value":{"entity-type":"item","numeric-id":5375501,"id":"Q5375501"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q758223$CA9CB4CA-1B2F-4EA7-AF56-BB270A038637","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"739e858e8e22022496808a5ab0ba523c59fd7496","datavalue":{"value":{"entity-type":"item","numeric-id":1182612,"id":"Q1182612"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0f35b109f16cbc7a9a3c90def542f73deec5c6b8","datavalue":{"value":{"amount":"+0.8934090733528137","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":"Q758223$5A65BF37-A7AD-446A-BCC1-8D75533FCE6B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a00c85c6346b6cba3df7141af165119d4ebf702c","datavalue":{"value":{"entity-type":"item","numeric-id":1904987,"id":"Q1904987"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c8c2152712c4311913a8992e4d5bbaff186e7660","datavalue":{"value":{"amount":"+0.8571625351905823","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":"Q758223$A0C05F15-BD95-4217-A524-12CAFF2CF2C8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e4f23ac60b327c82b053fc2c43b7650942c5def3","datavalue":{"value":{"entity-type":"item","numeric-id":3690239,"id":"Q3690239"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"144262f992491d4e6fa36b5706f5c8ccc79c321d","datavalue":{"value":{"amount":"+0.7959215044975281","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":"Q758223$C9DB8913-B140-44AF-8AD2-1C09B98A9DA4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"25079ea8f111b51e9e70f8f0fe2849468bd0c80d","datavalue":{"value":{"entity-type":"item","numeric-id":2105320,"id":"Q2105320"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e114e72c72ba6bc5a7773993d59cf4c6cf8fc6f0","datavalue":{"value":{"amount":"+0.744268536567688","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":"Q758223$0E4AA93C-0AC5-4AF9-9DD2-F22FA70B8A65","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"984f72aa54543bf6ee28e76a04552dbf9281f974","datavalue":{"value":{"entity-type":"item","numeric-id":5488104,"id":"Q5488104"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b696a3911920a3c93bb3fa3045dbb2369d758932","datavalue":{"value":{"amount":"+0.7115423083305359","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":"Q758223$04279BE0-5F4C-4CB9-98FD-AEAEFCEEB48E","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"An improved upper bound on the number of intersections between two rectangular paths","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/An_improved_upper_bound_on_the_number_of_intersections_between_two_rectangular_paths"}}}}}