Misplaced Pages

In mathematics, the Gilbert–Pollak conjecture is an unproven conjecture on the ratio of lengths of Steiner trees and Euclidean minimum spanning trees for the same point sets in the Euclidean plane. It was proposed by Edgar Gilbert and Henry O. Pollak in 1968.

Statement

For a set of points in the plane, the shortest network of line segments that connects the points, having only the given points as endpoints, is the Euclidean minimum spanning tree of the set. It may be possible to construct a shorter network by using additional endpoints, not present in the given point set. These additional points are called Steiner points and the shortest network that can be constructed using them is called a Steiner minimum tree. The Steiner ratio is the supremum, over all point sets, of the ratio of lengths of the Euclidean minimum spanning tree to the Steiner minimum tree. Because the Steiner minimum tree is shorter, this ratio is always greater than one.

A lower bound on the Steiner ratio is provided by three points at the vertices of an equilateral triangle of unit side length. For these three points, the Euclidean minimum spanning tree uses two edges of the triangle, with total length two. The Steiner minimum tree connects all three points to a Steiner point at the centroid of the triangle, with the smaller total length ${\displaystyle {\sqrt {3}}}$. Because of this example, the Steiner ratio must be at least ${\textstyle 2/{\sqrt {3}}\approx 1.155}$.

The Gilbert–Pollak conjecture states that this example is the worst case for the Steiner ratio, and that this ratio equals ${\displaystyle 2/{\sqrt {3}}}$. That is, for every finite point set in the Euclidean plane, the Euclidean minimum spanning tree can be no longer than ${\displaystyle 2/{\sqrt {3}}}$ times the length of the Steiner minimum tree.

Attempted proof

The conjecture is famous for its proof by Ding-Zhu Du and Frank Kwang-Ming Hwang, which later turned out to have a serious gap.

Based on the flawed Du and Hwang result, J. Hyam Rubinstein and Jia F. Weng concluded that the Steiner ratio is also ${\displaystyle 2/{\sqrt {3}}}$ for a 2-dimensional sphere of constant curvature, but due to the gap in the base result of Du and Hwang, the result of Rubinstein and Weng is now also considered as not proved yet.

References

1. Gilbert, E. N.; Pollak, H. O. (January 1968). "Steiner Minimal Trees". SIAM Journal on Applied Mathematics. 16 (1): 1–29. doi:10.1137/0116001. ISSN 0036-1399. S2CID 123196263.
2. ^ Du, D. Z.; Hwang, F. K. (1992-06-01). "A proof of the Gilbert-Pollak conjecture on the Steiner ratio". Algorithmica. 7 (1): 121–135. doi:10.1007/BF01758755. ISSN 0178-4617. S2CID 36038781.
3. Du, D. Z.; Hwang, F. K. (1990-12-01). "The Steiner ratio conjecture of Gilbert and Pollak is true". Proceedings of the National Academy of Sciences. 87 (23): 9464–9466. Bibcode:1990PNAS...87.9464D. doi:10.1073/PNAS.87.23.9464. ISSN 0027-8424. PMC 55186. PMID 11607122. S2CID 9811160.
4. Ivanov, A. O.; Tuzhilin, A. A. (2011-03-26). "The Steiner Ratio Gilbert–Pollak Conjecture Is Still Open". Algorithmica. 62 (1–2): 630–632. doi:10.1007/s00453-011-9508-3. S2CID 7486839.
5. Tuzhilin A., A.; Ivanov O., A (2014-02-25). "Du-Hwang Characteristic Area: Catch-22". arXiv:1402.6079 .
6. Rubinstein, J.; Weng, J. (1997-03-01). "Compression Theorems and Steiner Ratios on Spheres". Journal of Combinatorial Optimization. 1: 67–78. doi:10.1023/A:1009711003807. ISSN 1382-6905. S2CID 35145869.
7. Innami, N.; Kim, B.H.; Mashiko, Y.; Shiohama, K. (1990-11-15). "The Steiner Ratio Conjecture of Gilbert-Pollak May Still Be Open". Algorithmica. 57 (4): 869–872. doi:10.1007/s00453-008-9254-3. ISSN 0178-4617. S2CID 30809157.

• Conjectures
• Unsolved problems in graph theory
• Unsolved problems in computer science
• Geometric algorithms
• Combinatorial optimization
• Metric geometry