Optimum Steiner Ratio for Gradient-Constrained Networks Connecting Three Points in 3-Space, Part I
It is well known that when there is no gradient constraint, the minimum Steiner ratio for three terminals is achieved with an equilateral triangle, and the ratio is root 3/2. This article shows that in the gradient-constrained cases, the configuration of three terminals giving the minimum Steiner ratio is also an equilateral triangle. However, there are an infinite number of such triangles with differing orientations in 3-space. We determine the behavior of the Steiner ratio over all of these equilateral triangles and thereby show that the minimum ratio occurs when the triangle is in the vertical plane with one edge vertical. The minimum ratio tends to 3/4 as the value of the gradient constraint tends to zero. (C) 2008 Wiley Periodicals, Inc. NETWORKS, Vol. 53(2), 212-220 2009
gradient-constrained networks minimum networks steiner trees locally minimal