Abstract
LetL p be the plane with the distanced p (A 1 ,A 2 ) = (¦x 1 −x 2¦p + ¦y1 −y 2¦p)/1p wherex i andy i are the cartesian coordinates of the pointA i . LetP be a finite set of points inL p . We consider Steiner minimal trees onP. It is proved that, for 1 <p < ∞, each Steiner point is of degree exactly three. Define the Steiner ratio ϱ p to be inf{L s (P)/L m (P)¦P⊂L p } whereL s (P) andL m (P) are lengths of the Steiner minimal tree and the minimal spanning tree onP, respectively. Hwang showed ϱ1 = 2/3. Chung and Graham proved ϱ2 > 0.842. We prove in this paper that ϱ{∞} = 2/3 and √(√2/2)ϱ1ϱ2 ≤ ϱp ≤ √3/2 for anyp.
Similar content being viewed by others
References
F. R. K. Chung and R. L. Graham, A new bound for euclidean Steiner minimal trees,Ann. N. Y. Acad. Sci,440 (1985), 328–346.
F. R. K. Chung and F. K. Hwang, A lower bound for the Steiner tree problem,SIAM J. Appl. Math.,34 (1978), 27–36.
D. Z. Du, On Steiner ratio conjectures,Proceedings of NATO Advanced Research Workshop on Topological Network Designs, Denmark, 1989.
D. Z. Du and F. K. Hwang, A new bound for the Steiner ratio,Trans. Amer. Math. Soc.,278 (1983), 138–148.
D. Z. Du, F. K. Hwang, and E. N. Yao, The Steiner ratio conjecture is true for five points,J. Combin. Theory Ser. A,38 (1985), 230–240.
E. N. Gilbert and H. O. Pollak, Steiner minimal trees,SIAM J. Appl. Math.,16 (1968), 1–29.
R. L. Graham and F. K. Hwang, Remarks on Steiner minimal trees,Bull. Inst. Math. Acad. Sinica,4 (1976), 177–182.
F. K. Hwang, On Steiner minimal trees with rectilinear distance,SIAM J. Appl. Math.,30 (1976), 104–114.
H. O. Pollak, Some remarks on the Steiner problem,J. Combin. Theory Ser. A,24 (1978), 278–295.
J. H. Rubinstein and D. Thomas, The Steiner ratio conjecture for six points, Manuscript.
J. M. Smith and M. Gross, Steiner minimal trees and urban service networks,J. Soc. Econ. Plann.,16 (1982), 21–38.
Author information
Authors and Affiliations
Additional information
Communicated by F. K. Hwang.
This work was supported in part by the National Science Foundation of China and the President Foundation of Academia Sinica.
Rights and permissions
About this article
Cite this article
Liu, Z.C., Du, D.Z. On Steiner minimal trees withL p distance. Algorithmica 7, 179–191 (1992). https://doi.org/10.1007/BF01758757
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01758757