A short proof of a result of Pollak on Steiner minimal trees |
| |
Authors: | D.Z Du E.Y Yao F.K Hwang |
| |
Affiliation: | Institute of Applied Mathematics, Academia Sinica, Beijing, China;Bell Laboratories, Murray Hill, New Jersey 07974 USA |
| |
Abstract: | The long-standing conjecture of Gilbert and Pollak states that for any set of n given points in the euclidean plane, the ratio of the length of a Steiner minimal tree and the length of a minimal (spanning) tree is at least . This conjecture was shown to be true for n = 3 by Gilbert and Pollak, and for n = 4 by Pollak. However, the proof for n = 4 by Pollak is sufficiently complicated that no generalization to any other value of n has been found. We use a different approach to give a very short proof for the n = 4 case. This approach also allows us to attack the n = 5 case, though the proof is no longer short (to be reported in a subsequent paper). |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|