caa a22 4500 469074884 CHVBK 20180323132932.0 cr unu---uuuuu 170328e19920701xx s 000 0 eng 10.1007/BF02293036 doi (NATIONALLICENCE)springer-10.1007/BF02293036 Snyder Timothy Department of Computer Science, Georgetown University, 20057, Washington, DC, USA aut Worst-case minimum rectilinear steiner trees in all dimensions [Elektronische Daten] [Timothy Snyder] It is proved that the length of the longest possible minimum rectilinear Steiner tree ofn points in the unitd-cube is asymptotic toβ dn(d−1)/d , whereβ d is a constant that depends on the dimensiond≥2. A method of Chung and Graham (1981) is generalized to dimensiond to show that 1≤β d≤d4(1−d)/d . In addition to replicating Chung and Graham's exact determination ofβ 2=1, this generalization yields new bounds such as 1≤β 3<1.191 and % MathType!MTEF!2!1!+-% feaafiart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn% hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr% 4rNCHbGeaGqiVy0df9qqqrpepC0xbbL8F4rqqrFfpeea0xe9Lqpe0x% c9q8qqaqFn0dXdir-xcvk9pIe9q8qqaq-xir-f0-yqaqVeLsFr0-vr% 0-vr0xc8meaabaqaciGacaGaaeqabaWaaeaaeaaakeaaieaacaWFXa% GaeyizImQaeqOSdi2aaSbaaSqaaiaa-rdaaeqaaOGaeyizIm6aaOaa% aeaacaaIYaaaleqaaaaa!4122! $$1 \leqslant \beta _4 \leqslant \sqrt 2 $$ . Springer-Verlag New York Inc., 1992 Discrete & Computational Geometry Springer New York 8/1(1992-07-01), 73-92 0179-5376 8:1<73 1992 8 454 https://doi.org/10.1007/BF02293036 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/BF02293036 text/html Onlinezugriff via DOI NATIONALLICENCE 100 1- Snyder Timothy Department of Computer Science, Georgetown University, 20057, Washington, DC, USA aut NATIONALLICENCE 773 0- Discrete & Computational Geometry Springer New York 8/1(1992-07-01), 73-92 0179-5376 8:1<73 1992 8 454 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer