The sharp savings from junctions in planar connection networks
For a finite set $A \subset \mathbb{R}^2$ with at least two points, let $M(A)$ be the length of a Euclidean minimum spanning tree of $A$, a tree with straight edges and vertex set exactly $A$, and let $S(A)$ be the length of a Steiner minimal tree for $A$: the infimum of the lengths of finite trees with straight edges whose vertex sets contain $A$, additional vertices being allowed anywhere in the plane. For the vertices of an equilateral triangle, $S(A) = (\sqrt3/2)\, M(A)$. The inequality below was proved for sets of four points by Pollak, of five points by Du, Hwang and Yao (with a simpler proof by Friedel and Widmayer), and of six points by Rubinstein and Thomas. Chung and Graham proved $S(A) \ge 0.824\, M(A)$ for every $A$, and Ke, Huang, Shu, He, Gai and Wang improved the constant to $0.8559$ (2026). Du and Hwang published a proof of the inequality (1992), in which Innami, Kim, Mashiko and Shiohama (2010) and Ivanov and Tuzhilin (2012) pointed out gaps.
Problem. Is $S(A) \ge (\sqrt3/2)\, M(A)$ for every such $A$?
Source: Gilbert and Pollak (1968), the Steiner ratio conjecture.
Imported from github.com/MColbrook/AIM.
Classification
- Primary
- MG — Metric Geometry
- Secondary
- CO
- Keywords
- AIM Open Applied Problems, minimum spanning trees, Steiner minimal trees
References
@article{gilbert1968,
author = {Gilbert, E. N. and Pollak, H. O.},
title = {Steiner minimal trees},
journal = {SIAM J. Appl. Math.},
volume = {16},
number = {1},
year = {1968},
pages = {1--29},
doi = {10.1137/0116001},
}
@article{pollak1978,
author = {Pollak, H. O.},
title = {Some remarks on the {S}teiner problem},
journal = {J. Combin. Theory Ser. A},
volume = {24},
number = {3},
year = {1978},
pages = {278--295},
doi = {10.1016/0097-3165(78)90058-4},
}
@article{du1985,
author = {Du, D. Z. and Hwang, F. K. and Yao, E. Y.},
title = {The {S}teiner ratio conjecture is true for five points},
journal = {J. Combin. Theory Ser. A},
volume = {38},
number = {2},
year = {1985},
pages = {230--240},
doi = {10.1016/0097-3165(85)90073-1},
}
@article{friedel1989,
author = {Friedel, J. and Widmayer, P.},
title = {A simple proof of the {S}teiner ratio conjecture for five points},
journal = {SIAM J. Appl. Math.},
volume = {49},
number = {3},
year = {1989},
pages = {960--967},
doi = {10.1137/0149057},
}
@article{rubinstein1991,
author = {Rubinstein, J. H. and Thomas, D. A.},
title = {The {S}teiner ratio conjecture for six points},
journal = {J. Combin. Theory Ser. A},
volume = {58},
number = {1},
year = {1991},
pages = {54--77},
doi = {10.1016/0097-3165(91)90073-P},
}
@article{chung1985,
author = {Chung, F. R. K. and Graham, R. L.},
title = {A new bound for {E}uclidean {S}teiner minimal trees},
journal = {Ann. New York Acad. Sci.},
volume = {440},
number = {1},
year = {1985},
pages = {328--346},
doi = {10.1111/j.1749-6632.1985.tb14564.x},
}
@misc{ke2026,
author = {Ke, Yisi and Huang, Tianyu and Shu, Yankai and He, Di and Gai, Jingchu and Wang, Liwei},
title = {Towards solving the {G}ilbert--{P}ollak conjecture via large language models},
year = {2026},
eprint = {2601.22365},
archivePrefix = {arXiv},
note = {v3, 2 September 2026; ICML 2026},
}
@article{du1992,
author = {Du, D.-Z. and Hwang, F. K.},
title = {A proof of the {G}ilbert--{P}ollak conjecture on the {S}teiner ratio},
journal = {Algorithmica},
volume = {7},
number = {1-6},
year = {1992},
pages = {121--135},
doi = {10.1007/BF01758755},
}
@article{ivanov2012,
author = {Ivanov, A. O. and Tuzhilin, A. A.},
title = {The {S}teiner ratio {G}ilbert--{P}ollak conjecture is still open: clarification statement},
journal = {Algorithmica},
volume = {62},
number = {1-2},
year = {2012},
pages = {630--632},
doi = {10.1007/s00453-011-9508-3},
}
@misc{aim-planar-steiner-ratio,
author = {Brunton, Steve and Colbrook, Matthew J. and de Hoop, Maarten V. and Stepaniants, George and Townsend, Alex and Ward, Rachel},
title = {{The sharp savings from junctions in planar connection networks}},
howpublished = {AIM --- Open Applied Problems, GitHub repository},
year = {2026},
url = {https://github.com/MColbrook/AIM/blob/a153f469ee0ea64e876b2ad97c79d252c19a3e22/problems/276-planar-steiner-ratio.md},
note = {Entry 276 at commit a153f46, 2026-10-13},
}
Citing this problem
This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.
OP-00461, "The sharp savings from junctions in planar connection networks", clopen.solutions.