Abstract
A minimum Steiner tree for a given setX of points is a network interconnecting the points ofX having minimum possible total length. In this note we investigate various properties of minimum Steiner trees in normed planes, i.e., where the “unit disk” is an arbitrary compact convex centrally symmetric domainD having nonempty interior. We show that if the boundary ofD is strictly convex and differentiable, then each edge of a full minimum Steiner tree is in one of three fixed directions. We also investigate the Steiner ratioρ(D) forD, and show that, for anyD, 0.623<ρ(D)<0.8686.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
M. Alfaro, M. Conger, K. Hodges, A. Levy, R. Kochar, L. Kuklinski, Z. Mahmood, and K. von Haam, The structure of singularities of Φ-minimizing networks inR 2,Pacific J. Math. 149 (1991), 201–210.
G. D. Chakerian and M. A. Ghadehari, The Fermat problem in Minkowski space,Geom. Dedicata 17 (1985), 227–238.
E. J. Cockayne, On the Steiner problem,Canad. Math. Bull. 10 (1967), 431–450.
D. Z. Du and F. K. Hwang, A proof of Gilbert-Pollak's conjecture on the Steiner ratio,Algorithmica 7 (1992), 121–135.
D. Z. Du and F. K. Hwang, Reducing the Steiner problem in a normed plane,SIAM J. Comput. 21 (1992), 1001–1007.
M. R. Garey, R. L. Graham, and D. S. Johnson, The complexity of computing Steiner minimal trees,SIAM J. Appl. Math. 32 (1977), 835–859.
M. R. Garey and D. S. Johnson, The rectilinear Steiner tree problem is NP-complete,SIAM J. Appl. Math. 32 (1977), 826–834.
E. N. Gilbert and H. O. Pollak, Steiner minimal trees,SIAM J. Appl. Math. 178 (1968), 1–29.
F. K. Hwang, On Steiner minimal trees with rectilinear distance,SIAM J. Appl. Math. 30 (1976), 104–114.
G. Lawlor and F. Morgan, Paired calibrations applied to soapfilms, immiscible fluids, and surfaces or networks minimizing other norms, Preprint (1991).
Z. C. Liu and D. Z. Du, On Steiner minimal trees withL p distance,Algorithmica 7 (1992), 179–191.
Z. A. Melzak,Companion to Concrete Mathematics, Vol. II, Wiley, New York, 1976.
D. Sankoff and P. Rousseau, Locating the vertices of a Steiner tree in an arbitrary metric space,Math. Programming 9 (1975), 240–246.
M. Sarrafzadeh and C. K. Wong, Hierarchical Steiner tree construction in uniform orientations, Unpublished manuscript.
J. M. Smith and M. Gross, Steiner minimal trees and urban service networks,J. Sociol. Econ. Planning 16 (1982), 21–38.
D. Cieslik, Das Steiner-Problem in Banach-Minkowski-Räumen, Habilitationsschrift, Ernst-Moritz-Arnot-Universität, Greifswald, 1991.
Author information
Authors and Affiliations
Additional information
Part of this work was done while Ding-Zhu Du was at the Computer Science Department, Princeton University and the Center for Discrete Mathematics and Theoretical Computer Science at Rutgers. Supported by NSF under Grant STC88-09648.
Rights and permissions
About this article
Cite this article
Du, DZ., Gao, B., Graham, R.L. et al. Minimum steiner trees in normed planes. Discrete Comput Geom 9, 351–370 (1993). https://doi.org/10.1007/BF02189328
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/BF02189328