A variational approach to the Steiner network problem |
| |
Authors: | J H Rubinstein D A Thomas |
| |
Institution: | (1) Mathematics Department, Melbourne University, 3052 Parkville, Victoria, Australia |
| |
Abstract: | Supposen points are given in the plane. Their coordinates form a 2n-vectorX. To study the question of finding the shortest Steiner networkS connecting these points, we allowX to vary over a configuration space. In particular, the Steiner ratio conjecture is well suited to this approach and short proofs of the casesn=4, 5 are discussed. The variational approach was used by us to solve other cases of the ratio conjecture (n=6, see 11] and for arbitraryn points lying on a circle). Recently, Du and Hwang have given a beautiful complete solution of the ratio conjecture, also using a configuration space approach but with convexity as the major idea. We have also solved Graham's problem to decide when the Steiner network is the same as the minimal spanning tree, for points on a circle and on any convex polygon, again using the variational method. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|