Abstract
Fifty years ago Jarnik and Kössler showed that a Steiner minimal tree for the vertices of a regularn-gon contains Steiner points for 3 ≤n≤5 and contains no Steiner point forn=6 andn≥13. We complete the story by showing that the case for 7≤n≤12 is the same asn≥13. We also show that the set ofn equally spaced points yields the longest Steiner minimal tree among all sets ofn cocircular points on a given circle.
Article PDF
Similar content being viewed by others
References
F. R. K. Chung and R. L. Graham, Steiner trees for ladders,Ann. Discrete Math. 2 (1978), 173–200.
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.
D. Z. Du and F. K. Hwang, A new bound for the Steiner ratio,Trans. Amer. Math. Soc. 228 (1983), 137–148.
D. Z. Du and F. K. Hwang, Steiner minimal trees for bar waves, to appear.
D. Z. Du, F. K. Hwang, and J. F. Weng, Steiner minimal trees on zig-zag line,Trans. Amer. Math. Soc. 228 (1983), 149–156.
D. Z. Du, F. K. Hwang, J. F. Weng, and S. C. Chao, Steiner minimal trees for points on a circle.Proc. Amer. Math. Soc.,95 (1985), 613–618.
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.
E. N. Gilbert and H. O. Pollak, Steiner minimal trees,SIAM J. Appl. Math. 16 (1968), 1–29.
F. K. Hwang, J. F. Weng, and D. Z. Du, A class of full Steiner minimal trees,Discrete Math. 45 (1983), 107–112.
V. Jarnik and M. Kössler, O minimálnich grafech obbsahujicich n daných bodu,Časopis Pěst. Mat. Fys. 63 (1934), 223–235.
A. Kotzig, Optimálne spojovacie systémy, inMathematick�� metódy V Hospodárskej Praxi (V. Kapitoly, ed.), Vydavel'stuo Solvenskej Akadémie vied, Bratislava, 1961.
Z. A. Melak, On the problem of Steiner,Canad. Math. Bull. 4 (1960), 143–148
J. F. Weng and F. K. Hwang, Hexagonal coordinate system and Steiner minimal trees,Discrete Math., to appear.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Du, D.Z., Hwang, F.K. & Weng, J.F. Steiner minimal trees for regular polygons. Discrete Comput Geom 2, 65–84 (1987). https://doi.org/10.1007/BF02187871
Received:
Revised:
Published:
Issue date:
DOI: https://doi.org/10.1007/BF02187871