Disproofs of Generalized Gilbert–Pollak Conjecture on the Steiner Ratio in Three or More Dimensions
✍ Scribed by Ding-Zhu Du; Warren D. Smith
- Publisher
- Elsevier Science
- Year
- 1996
- Tongue
- English
- Weight
- 389 KB
- Volume
- 74
- Category
- Article
- ISSN
- 0097-3165
No coin nor oath required. For personal study only.
✦ Synopsis
The Gilbert Pollak conjecture, posed in 1968, was the most important conjecture in the area of Steiner trees.'' The Steiner minimal tree'' (SMT) of a point set P is the shortest network of wires'' which will suffice to electrically'' interconnect P. The minimum spanning tree'' (MST) is the shortest such network when only intersite line segments are permitted. The generalized GP conjecture stated that \ d =inf P/R d (l SMT (P)Âl MST (P)) was achieved when P was the vertices of a regular d-simplex. It was showed previously that the conjecture is true for d=2 and false for 3 d 9. We settle remaining cases completely in this paper. Indeed, we show that any point set achieving \ d must have cardinality growing at least exponentially with d. The real question now is: What are the true minimal-\ point sets ? This paper introduces the d-dimensional sausage'' point sets, which may have a lit to do with the answer.