{"entities":{"Q1566725":{"pageid":1577465,"ns":120,"title":"Item:Q1566725","lastrevid":70727148,"modified":"2026-04-13T16:21:53Z","type":"item","id":"Q1566725","labels":{"en":{"language":"en","value":"The Steiner tree problem for terminals on the boundary of a rectilinear polygon"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1454563"}},"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":"Q1566725$AB8328E0-0D55-4250-A9F8-744257C127EA","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"fa089237c83cc7b5495c5495b2ebbc234149345f","datavalue":{"value":{"text":"The Steiner tree problem for terminals on the boundary of a rectilinear polygon","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1566725$71BEF04F-7788-4405-BBF4-D05C61848022","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"fabb58ca0fff439582ec5956d855433a54a7bb88","datavalue":{"value":"0939.68090","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1566725$A6EC2A55-EBC9-4B3A-A7AF-D3652ED31FB7","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"3230175590c38140d6559a7a565355fb47b371d7","datavalue":{"value":"10.1016/S0304-3975(98)00171-6","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1566725$9FB18780-FA57-43C1-A351-56D09634B331","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":"Q1566725$4DC6E341-477D-4036-8596-06EA2F1289CF","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"cea4e04940bd3504f3c0f2b605e025bc106fb722","datavalue":{"value":{"time":"+2000-06-04T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1566725$E0EAA2BF-F44A-44DC-8BC9-4B75F49B3481","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"580d3d1576e41014c55450de71b552ed93eb55d9","datavalue":{"value":"Given a simple rectilinear polygon P with \\(k\\) sides and \\(n\\) terminals on its boundary, we present an \\(O(k^{3}n)\\)-time algorithm to compute the minimal rectilinear Steiner tree lying inside P interconnecting the terminals. We obtain our result by proving structural properties of a selective set of minimal Steiner trees and exploiting them in a dynamic programming algorithm.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1566725$F65953C6-E1F7-4128-955D-4AF7A6F73BCE","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1566725$88FA4C55-EED0-4106-9AB1-0ED2E83F9477","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"aa3ca91474fff28e420d9cace433f8447ec799b0","datavalue":{"value":"90C39","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1566725$753F3AFA-0A6F-4E7E-9C96-33FF115BFB14","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"42219ec8714c3426c5490edd92eb4bd01a084d57","datavalue":{"value":"1454563","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1566725$6F3D5C74-9554-4BE0-BFFD-83D6A278D68D","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b504ff4b6dbafd2d1ef6e681b6bbc085753d6504","datavalue":{"value":"Rectilinear Steiner tree","type":"string"},"datatype":"string"},"type":"statement","id":"Q1566725$1566B27C-F21F-46B8-8E63-6638F68EE444","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9954453c455938801bc269861c27676037205fdb","datavalue":{"value":"Homotpic routing","type":"string"},"datatype":"string"},"type":"statement","id":"Q1566725$20B194D8-5E77-4B70-9A19-7D6DA88A8E3D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e7a17b3a19b73777fb334e50e0d5cc88736fd6f2","datavalue":{"value":"Dynamic programming","type":"string"},"datatype":"string"},"type":"statement","id":"Q1566725$1F7AF006-A3E2-4B9B-88D4-720383852DD2","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"3ba5aa216f2d6584c6b877fd61e686d62b452d3e","datavalue":{"value":{"entity-type":"item","numeric-id":331367,"id":"Q331367"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1566725$3AD58A16-A471-4243-8D74-D1ABCFC716F7","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":"Q1566725$CB479ABD-458B-43C1-828C-638579ED106F","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"eefcfb005ca1a84140ceb7ea0794f9c1b3d1b2ad","datavalue":{"value":{"entity-type":"item","numeric-id":3487159,"id":"Q3487159"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1566725$BB924919-52FE-471E-BA6E-0514B5EB9370","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2a661769b64711d37b8c93fc0e62e6ad393dd736","datavalue":{"value":{"entity-type":"item","numeric-id":4206584,"id":"Q4206584"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1566725$E34A011F-A78E-4868-881B-6C3CEC6EACBC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ea9860158092a09e2c7c043eabaac54be373acbd","datavalue":{"value":{"entity-type":"item","numeric-id":4525722,"id":"Q4525722"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1566725$914AE7FD-2D75-4251-8BA2-6B5B0C22978B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0172ba1b6d6a71dfada5ea07ead90ea9385b47a4","datavalue":{"value":{"entity-type":"item","numeric-id":3789369,"id":"Q3789369"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1566725$7F66241E-143E-469D-9755-3822E238C284","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2eb143109603ec0831472adeaf404a9410e6658d","datavalue":{"value":{"entity-type":"item","numeric-id":1186799,"id":"Q1186799"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1566725$017D31D9-BD23-4439-8B73-76910D2669EB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b50f79d2d5212f6934b39d3117f59f05b0477f28","datavalue":{"value":{"entity-type":"item","numeric-id":6487979,"id":"Q6487979"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1566725$6F9C0458-E071-4735-9A98-C06B94C48FD5","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"08ee472a71d6c73d852395d9512ff08ad2f813bc","datavalue":{"value":"Q127814583","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1566725$5FA9F37C-4E15-4FC1-B322-2172D09217DB","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f1ee79f341c02b8222b637bdcdef54ac6cac7d9e","datavalue":{"value":{"entity-type":"item","numeric-id":4395320,"id":"Q4395320"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3ed0d4a8002d98ae475e924c65685a1d36c2409a","datavalue":{"value":{"amount":"+1.0000001","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1566725$2F2B1B8C-B2A5-4EC9-86F9-CB51E1D886E5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6895f491fb3f48155ed10b6029d4e628b3728a19","datavalue":{"value":{"entity-type":"item","numeric-id":4242784,"id":"Q4242784"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1bb2265197df333b94eb7d6de74e9cc4a6e7c198","datavalue":{"value":{"amount":"+0.92398417","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1566725$ACE7A648-AF44-4E5D-9BF3-B8BCEEA45D5E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0d354f7c9e9bb74bc166deccbcd1385103c2e396","datavalue":{"value":{"entity-type":"item","numeric-id":3196405,"id":"Q3196405"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d4bf93fb5a2f266ced140f0eaceed487a1670c8e","datavalue":{"value":{"amount":"+0.92099977","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1566725$F9E73C40-F5BC-4FF1-9092-27CBA94DA483","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e92cc2d49e929c0d1c49c28dc4ca67ed4701335c","datavalue":{"value":{"entity-type":"item","numeric-id":3487159,"id":"Q3487159"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5491d703497a605645b193d8e0d327cdf2de2a47","datavalue":{"value":{"amount":"+0.9169733","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1566725$A840FC41-DA4D-4530-9CD7-6B4BA7CA604F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8079f07bbc7f8a558ebbd8ea62c2b43c038c3a47","datavalue":{"value":{"entity-type":"item","numeric-id":1186802,"id":"Q1186802"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"027ef5b87cb63d8072e2599fdcf0d2bc7f9beabf","datavalue":{"value":{"amount":"+0.9166432","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1566725$7920F0E6-FD35-4311-94FD-DCF95B01205F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9b056b40c689641d2b5e6e39449aa329f35bb26c","datavalue":{"value":{"entity-type":"item","numeric-id":4967230,"id":"Q4967230"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fc1eb5fbeaafd71f99ae72ee3f4f132721a96d28","datavalue":{"value":{"amount":"+0.91285974","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1566725$3FEE5314-5A07-4D20-817C-D152C33A3E91","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e8d2b98577fe70f2d8ab58bb5d77718ba00271f0","datavalue":{"value":{"entity-type":"item","numeric-id":1014425,"id":"Q1014425"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3ac99179badf15eb43bdc12b8594461f63b09205","datavalue":{"value":{"amount":"+0.9117312","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1566725$5C9A21D9-20D6-49ED-B347-6FCC19CCDB14","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0de780abc68072c9b4e08df2b6571e74f301112d","datavalue":{"value":{"entity-type":"item","numeric-id":1853109,"id":"Q1853109"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b2efc9527a348d1930a1275ac35bb216ed87149b","datavalue":{"value":{"amount":"+0.9114175","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1566725$1A0BB4A9-306F-4003-859C-A1BEC3A90BE1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"dcc5085a765dde1b162b5a3d2b379252a0fa7308","datavalue":{"value":{"entity-type":"item","numeric-id":826086,"id":"Q826086"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9c25fcb69692cf8f7eda643f0a975b425c12439f","datavalue":{"value":{"amount":"+0.9103627","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1566725$081DA4EE-30FF-47B6-ADF6-1C45B044AE5A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cf78af1a11d6cff4dd774569f7c88bf6ef02e636","datavalue":{"value":{"entity-type":"item","numeric-id":1969944,"id":"Q1969944"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"41e2119a28991f2a327261b2329090f57cfe6918","datavalue":{"value":{"amount":"+0.90938574","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1566725$B8BFAAB8-9A4D-422D-98FD-C0632A0289C4","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"The Steiner tree problem for terminals on the boundary of a rectilinear polygon","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/The_Steiner_tree_problem_for_terminals_on_the_boundary_of_a_rectilinear_polygon"}}}}}