{"entities":{"Q1192611":{"pageid":1203360,"ns":120,"title":"Item:Q1192611","lastrevid":70245063,"modified":"2026-04-13T13:28:06Z","type":"item","id":"Q1192611","labels":{"en":{"language":"en","value":"Worst-case minimum rectilinear Steiner trees in all dimensions"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 61213"}},"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":"Q1192611$406F262A-A6F6-48F4-A104-9399C4E32EAC","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"a2e5d68d62ad09d5a7c9031462b3821991b84403","datavalue":{"value":{"text":"Worst-case minimum rectilinear Steiner trees in all dimensions","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1192611$A1FBC90F-3A8E-428C-86C4-B1C9E1D61659","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"880e25213811863e6721478d8e7667053dbbf689","datavalue":{"value":"0783.05041","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1192611$7069D627-A000-4C4C-B27A-C22E89BD29B4","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"cf47a7b9e594795059871eb8dc00cad61cdbdf86","datavalue":{"value":"10.1007/BF02293036","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1192611$FE598CD8-ACA2-46B5-8B8F-9B8D955C134F","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"39061f166c1322bb73a88755f084b43e8de6d023","datavalue":{"value":{"entity-type":"item","numeric-id":750174,"id":"Q750174"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1192611$16E94855-60F9-4802-B6DA-9DF6EA6D679B","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":"Q1192611$83D54F62-F25C-47FC-916B-FA5599261CB4","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"5fd62271fe98c7ff9916cafed51cf35315eeeb31","datavalue":{"value":{"time":"+1992-09-27T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1192611$5099F305-6180-44AD-BD41-4EA236E81419","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"009bc974972b490e71f9bb5a41ee4ed352d24858","datavalue":{"value":"In this paper the distance between two points \\(x=(x_ 1,\\ldots,x_ d)\\) and \\(y=(y_ 1,\\ldots,y_ d)\\) of \\([0,1]^ d\\) in the Manhattan metric is \\(d_ R(x,y)=| x_ 1-y_ 1 |+\\cdots+| x_ d-y_ d |\\). For \\(S\\subseteq[0,1]^ d\\) let \\(L(S)\\) be the minimum length of a Steiner tree in the Manhattan metric. Then \\(s^*(n)=\\max \\bigl\\{ L(S):S \\subseteq [0,1]^ d,\\;| S |=n \\bigr\\}\\) is the ``worst-case length of a minimum rectilinear Steiner tree'' of \\(n\\) points in the unit cube. The following nice results are proved. Let \\(d \\geq 2\\). (1) There exists some constant \\(\\beta_ d>0\\) such that \\(s^*(n)\\sim \\beta_ dn^{(d-1)/d}\\) \\((d \\geq 2,\\;n \\to \\infty)\\). (2) \\(1 \\leq \\beta_ d \\leq d4^{(1-d)/d}\\).   The paper gives a useful historical account and generalizes methods of \\textit{F. R. K. Chung} and \\textit{R. L. Graham} [Geom. Dedicata 11, No. 3, 353-361 (1981; Zbl 0475.05023)]. The exact determination of \\(\\beta_ d\\), \\(d \\geq 3\\), remains as an open problem.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1192611$AC9270FB-FCD8-4FA2-AABB-66D960C73373","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"d5da87a72c21717089feda882f568938059a9d84","datavalue":{"value":"05C05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1192611$69076F13-05C1-4815-B322-C87E081D0F64","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"35cb8465ca85ba26995d54be2905dc35556d665c","datavalue":{"value":"90C27","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1192611$45F42E21-40EE-4283-AF4B-5E14D757F481","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"9afee452caa837a15ea420fe7555ea55fdf8aa37","datavalue":{"value":"61213","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1192611$24BDD2E5-0F2B-48AA-B7CE-960EF34EB5CA","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b995b9d468569d694c0cba480f8ef8954627bfbf","datavalue":{"value":"Manhattan metric","type":"string"},"datatype":"string"},"type":"statement","id":"Q1192611$206CD20F-B077-44B2-A5C0-18CBED546E27","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"66a0382610d9d9e28ef95c946357abf690b72349","datavalue":{"value":"Steiner tree","type":"string"},"datatype":"string"},"type":"statement","id":"Q1192611$0CA7F654-AF7F-450A-B9BE-D0D8F1E096A7","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":"Q1192611$7A53047E-CA2D-42E1-A45B-9E680ACA508B","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"a2ecbadb905930ae081fb4980e3c5f1fcc21a123","datavalue":{"value":{"entity-type":"item","numeric-id":5729634,"id":"Q5729634"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1192611$54E133E1-E6DF-4609-BD01-0E330A71EC93","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"20154dcd6acc7707e71c00f6cb546d453899fea1","datavalue":{"value":{"entity-type":"item","numeric-id":1105495,"id":"Q1105495"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1192611$8E75764D-2CEE-4561-A6E9-EAB8B0B1DE8B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"94765fb846bed352148d9e13a9cf76ce38cb42b1","datavalue":{"value":{"entity-type":"item","numeric-id":1159677,"id":"Q1159677"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1192611$22A1796A-A797-44BF-A35C-2CCD62900141","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e7b7c13f8756ac0aac8a4f3631a388b8627f48a5","datavalue":{"value":{"entity-type":"item","numeric-id":4186240,"id":"Q4186240"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1192611$3C9F9EE4-E6C2-41F3-B428-CD9B02119DBF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"616fd337be358f72ecbd5fb15280bf1136f48c0c","datavalue":{"value":{"entity-type":"item","numeric-id":3228026,"id":"Q3228026"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1192611$29473BFF-325B-44E9-97BA-B3B42F640A16","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7431b8bc1af7a6351e7c2d86660f496894ee616d","datavalue":{"value":{"entity-type":"item","numeric-id":4155835,"id":"Q4155835"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1192611$76D8050C-E0BA-4A08-B4A3-DA5282F59616","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f89a031afe32dfcbf4f8fba11966dba55c1408ae","datavalue":{"value":{"entity-type":"item","numeric-id":4179026,"id":"Q4179026"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1192611$AFCBEB2F-ED97-4CEF-8EC0-CBDE7DBF24B3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fda81e3d0e39c06434c8c6ab9bc988f021f6baca","datavalue":{"value":{"entity-type":"item","numeric-id":5542568,"id":"Q5542568"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1192611$FCFFCE87-9594-4F46-A54C-730DAF32DDE7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"02832b8a6716657731d6d7eb439a29c768293a26","datavalue":{"value":{"entity-type":"item","numeric-id":1111946,"id":"Q1111946"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1192611$7281B481-2203-4A29-8589-357DE8401719","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1fa4fad94b00c1283cfbf9a93a1abd9c2ff4c6dd","datavalue":{"value":{"entity-type":"item","numeric-id":5530464,"id":"Q5530464"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1192611$6EB07C48-F1F6-4B98-A755-D1274D045871","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6cff460e5532d881b857f2a3d6565f94019b1cbd","datavalue":{"value":{"entity-type":"item","numeric-id":4083448,"id":"Q4083448"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1192611$E8C686F8-CD4F-4F2D-85A1-68348E785812","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a18a2f58f1650ac507eb0eb745f6c30bb46f3424","datavalue":{"value":{"entity-type":"item","numeric-id":4731207,"id":"Q4731207"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1192611$50B4D8D3-5DB4-4F11-A84E-A0C8497C0FEF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f815a6001a60c9b40e3cc96122274c9a3a835ae4","datavalue":{"value":{"entity-type":"item","numeric-id":3283373,"id":"Q3283373"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1192611$41DBFE30-1D6B-45BE-9288-78C706FA7B86","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0f0bd60fc76d75b4e1c8cbc8244987514439a641","datavalue":{"value":{"entity-type":"item","numeric-id":762465,"id":"Q762465"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1192611$90EE1512-B416-4B12-A707-B3DCE2AEFBFB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4bc4a89840b6ca6ff4d9246191d700e74148dd02","datavalue":{"value":{"entity-type":"item","numeric-id":4077102,"id":"Q4077102"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1192611$E2924D94-E9D0-4A58-A060-0DEB2EFFCA4F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3d440e0b291165ed8e3430b8d3bd2f964886bf4f","datavalue":{"value":{"entity-type":"item","numeric-id":750175,"id":"Q750175"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1192611$CE469E94-3A9E-4AB7-89DA-5F3A48BD5ADF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0df02b6e3a7bf3c0d4babaf9c5d777e9afd84a5d","datavalue":{"value":{"entity-type":"item","numeric-id":3990108,"id":"Q3990108"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1192611$F3D13DF6-EC38-4AFF-BD55-DBEFED088B53","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f396b0fecde991325e5d1c8fbe3ecc7fce878152","datavalue":{"value":{"entity-type":"item","numeric-id":3204344,"id":"Q3204344"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1192611$8423DAF7-80AD-4A84-9D22-9615AD294044","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bd9c902e18f256ef6ab9ecbbe60131e5487ac544","datavalue":{"value":{"entity-type":"item","numeric-id":1152627,"id":"Q1152627"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1192611$CA413BD3-5B18-4EC0-9EB2-DF781EBF983C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"093272041b3d9e95afbb499643d38717b589b7a9","datavalue":{"value":{"entity-type":"item","numeric-id":3829359,"id":"Q3829359"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1192611$7E63F0A4-727F-41D1-9CA2-BE15E089A310","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6dc0559f16eedea55606af419809593245a47014","datavalue":{"value":{"entity-type":"item","numeric-id":3967062,"id":"Q3967062"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1192611$F4786DCF-B1C0-4D87-9184-EAA0E40ED4B8","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"2d791a9e31563825736112f861e15b8e66fc5992","datavalue":{"value":"https://doi.org/10.1007/bf02293036","type":"string"},"datatype":"url"},"type":"statement","id":"Q1192611$F6645AF6-DE25-4DA1-AAA2-FAD0CCF59A62","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"9e006aacd6ffa26740aec6825ba3a9b4768ae8e1","datavalue":{"value":"W2764860633","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1192611$0DBD2CBB-FCC5-481E-AC9D-2A6756020EE6","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3eecfb3330089d464f0075d0b7a4164e59951027","datavalue":{"value":{"entity-type":"item","numeric-id":1202044,"id":"Q1202044"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c4e30e8648aab492d600d02dbefd0ec772c5388f","datavalue":{"value":{"amount":"+0.8311717510223389","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":"Q1192611$241C18D1-8ED1-4AEE-B3CA-91EF35EB97F1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"de08084b7f4a7a0fb10693caaec08edf9d64f809","datavalue":{"value":{"entity-type":"item","numeric-id":1186795,"id":"Q1186795"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"231389eac0a48cddffe4e75658bd70ea4e2ddaa1","datavalue":{"value":{"amount":"+0.8176493644714355","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":"Q1192611$EFAF3B64-B9B5-47CE-BB82-78BF8E82E445","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c20e122ffaaed66ec0e93a0dff4420b8fefa7e47","datavalue":{"value":{"entity-type":"item","numeric-id":5323363,"id":"Q5323363"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"70a796875f243adc016b7f81eb07b655af8b1373","datavalue":{"value":{"amount":"+0.816980242729187","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":"Q1192611$161E082A-6F78-4DB9-AF04-166B3904F590","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fd9d121608176027e18645f82a9c8cbfc460a20b","datavalue":{"value":{"entity-type":"item","numeric-id":2764995,"id":"Q2764995"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6e65c624dbe1ec0ffdb2fe1ab655112d7a81828e","datavalue":{"value":{"amount":"+0.8168014883995056","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":"Q1192611$C79E804D-09A0-4907-AD61-A0FE35579739","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Worst-case minimum rectilinear Steiner trees in all dimensions","badges":[]}}}}}