Abstract
SupposeX is a convex configuration with radius of maximum curvaturer and at most one of the edges joining neighboring points has length strictly greater thanr. We use the variational approach to show the Steiner treeS coincides with the minimal spanning tree and consists of all these edges with a longest edge removed. This generalizes Graham's problem for points on a circle, which we had solved. In addition we describe the minimal spanning tree for certain convex configurations.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
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.
R. L. Graham, Some Results on Steiner Minimal Trees, Unpublished manuscript, 11 May 1967.
Z. A. Melzak, On the Problem of Steiner,Canad. Math. Bull. 4 (1961), 143–148.
J. H. Rubinstein and D. A. Thomas, A Variational Approach to the Steiner Network Problem,Ann. Oper. Res. 33 (1991), 481–499.
J. H. Rubinstein and D. A. Thomas, The Steiner Ratio Conjecture for Six Points,J. Combin. Theory Ser. A 58 (1991), 54–77.
J. H. Rubinstein and D. A. Thomas, The Steiner Ratio Conjecture for Cocircular Points,Discrete Comput. Geom. 7 (1992), 77–86.
J. H. Rubinstein and D. A. Thomas, Graham's Problem on Shortest Networks for Points on a Circle,Algorithmica 7 (1992), 193–218.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Thomas, D.A., Rubinstein, J.H. & Cole, T. The steiner minimal network for convex configurations. Discrete Comput Geom 9, 323–333 (1993). https://doi.org/10.1007/BF02189325
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/BF02189325