Gilbert–Pollack conjecture
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.[1]
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.[2]
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 [math]\displaystyle{ \sqrt 3 }[/math]. Because of this example, the Steiner ratio must be at least [math]\displaystyle{ 2/\sqrt 3\approx 1.155 }[/math].[2]
The Gilbert–Pollak conjecture states that this example is the worst case for the Steiner ratio, and that this ratio equals [math]\displaystyle{ 2/\sqrt 3 }[/math]. That is, for every finite point set in the Euclidean plane, the Euclidean minimum spanning tree can be no longer than [math]\displaystyle{ 2/\sqrt 3 }[/math] times the length of the Steiner minimum tree.[2]
Attempted proof
The conjecture is famous for its proof by Ding-Zhu Du and Frank Kwang-Ming Hwang,[3][2] which later turned out to have a serious gap.[4][5]
Based on the flawed Du and Hwang result, J. Hyam Rubinstein and Jia F. Weng concluded that the Steiner ratio is also [math]\displaystyle{ 2/\sqrt 3 }[/math] for a 2-dimensional sphere of constant curvature,[6] 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.[7]
References
- ↑ 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.
- ↑ 2.0 2.1 2.2 2.3 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.
- ↑ 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. doi:10.1073/PNAS.87.23.9464. ISSN 0027-8424. PMID 11607122. Bibcode: 1990PNAS...87.9464D.
- ↑ 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.
- ↑ Tuzhilin A., A.; Ivanov O., A (2014-02-25). "Du-Hwang Characteristic Area: Catch-22". arXiv:1402.6079 [math.MG].
- ↑ 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.
- ↑ 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.
 |  |
