A 75 Angle Constraint for Plane Minimal T1 Trees

Journal of Combinatorial Optimization, 4, 271–284, 2000 c 2000 Kluwer Academic Publishers. Manufactured in The Netherlands. °

A 75◦ Angle Constraint for Plane Minimal T1 Trees T. COLE Department of Electronic and Electrical Engineering, Tokyo Institute of Technology, Meguro-Ku, Tokyo 152, Japan Received April 5, 1996; Revised January 11, 1999; Accepted January 18, 1999

Abstract. In this paper it is shown that the minimum angle between any 2 edges of an Euclidean plane minimal T1 tree, or 3-size Steiner tree, is at least 75◦ . Keywords: Steiner minimal tree, T1 tree, Q-component

Introduction Let X n = {x1 , x2 , . . . , xn } denote a finite collection of n Euclidean plane (regular points). A Steiner minimal tree SMT is a shortest length network interconnecting X n where (1) all angles between edges are at least 120◦ and (2) there may be extra points, called Steiner points. It is called full if there are exactly n − 2 Steiner points and all edges meet at exactly 120◦ . The underlying graph of a Steiner tree is called the topology. A T1 tree, or 3-size Steiner tree (Du et al., 1991), interconnecting X n consists of spanning edges and minimal Steiner trees that interconnect 3 regular points, called Q-components. A minimal (shortest length) T1 tree may contain edges meeting at angles less than 120◦ and it is conjectured that L SMT /L T1 ≥ 0.93185... where L SMT is the length of a Steiner minimal tree and L T1 is the length of a minimal T1 tree. The value 0.93185... may be obtained from 4 points lying as the corners of a square. In this paper it is shown that the angle between any 2 edges of a minimal T1 tree must be least 75◦ . The variational approach For a full discussion see Rubinstein and Thomas (1991). Let X n = {x1 , x2 , . . . , xn } be n Euclidean plane points and G and G 0 be two separate trees each interconnecting X n with G consisting of k edges. Also suppose G and G 0 have length L G and L G 0 respectively. Let ρ = L G /L G 0 be defined as a ρ = R k → R function over the domain 1 of the edge lengths of G. If infρ = ρo , then the first derivative Dρ (v) of ρ in the direction of a vector ˙ ˙ v is LLGG0 ( LL˙ G0 − ρo ). Thus if L˙ G < (>)0 and L˙ G / L˙ G 0 > (<)0 then Dρ (v) < (>)0. G

Theorem 1. Let X n = {x1 , x2 , . . . , xn } denote a finite collection of n Euclidean plane points and suppose T is a minimal T1 tree interconnecting X n . Then any two edges of T meet at an angle of at least 75◦ .

272

COLE

Before proving this theorem the following lemmas will be considered. Lemma 1. Let x20 , x3 , x40 , x50 be the corners of a square such that x20 lies at the “origin”, x 3 lies on the “positive y-axis” and x50 lies on the “positive x-axis”. Let | | be the length function. As shown in figure 1, let b be the third point of the equilateral triangle 1bx40 x50 , lU be a line passing through x 3 x40 , I L , be a line passing through x 20 x50 , l 0 be a line passing through x3 and b, C0 be a circular arc of radius |x20 x3 | centered at x20 , p be the intersection point of C 0 and l 0 , 1x4 x5 o be an equilateral triangle of side length at most |x3 o| such that

Figure 1.

The positioning of 1x4 x5 o.

273

PLANE MINIMAL T1 TREES

o lies on l 0 between b and p, x40 lies above l 0 , and x50 lies below l 0 and outside C 0 . Also let δ be the angle measured clockwise at x4 from a line parallel with x20 x3 to x4 x5 . Then (i) if x 4 x5 is parallel to x20 x3 (i.e. δ = 0) then x4 lies below lU . (ii) if x4 lies above lU then δ ≥ 0. Proof:

Let q 0 be a line passing through x40 x50 .

(i) If x5 lies on the right hand side of q 0 then clearly x4 lies below lU . If x4 lies on the left hand side of q 0 then let z o be the point of intersection of l 0 and x40 x50 . Then |z o x50 |/|x40 x50 | = cos 30◦ · tan 15◦ + 0.5. It is only necessary to consider when x5 lies on C 0 . Let z be the intersection point of l 0 and x4 x5 , w be the intersection point of lU and a line passing through x4 and x5 . If θ = 6 x50 x20 x5 , then |zx5 | = |x20 x3 |(1 − sin θ − cos θ · tan 15◦ ),

|wx5 | = |x20 x3 |(1 − sin θ ),

and ¡p ¢ |zx5 | |z o x 0 | 3/2 · tan 15◦ + 0.5 = 0 50 = 1 − (cos θ · tan 15◦ )/(1 − sin θ ) ≤ |wx5 | |x4 x5 | for 0◦ ≤ θ ≤ 60◦ . Thus X 4 must lie below lU . Note that at θ = 60◦ , p = x5 . (ii) If x4 lies on the right hand side of q 0 then δ > 0. If x4 lies on the left hand side of q 0 then suppose x4 lies above lU and δ < 0. It will be shown that x5 lies in C 0 . Note that it is only necessary to consider when x4 lies on lU . By definition o lies on l 0 . Thus if o = b, then x 5 will lie inside C 0 on a line, l 00 , 60◦ to lL at x50 . (When x4 = x3 or x 4 = x40 , x5 lies on C 0 ). As o moves along l 0 toward p, x5 will clearly remain inside C 0 . When x5 x4 is parallel to x20 x3 , i.e. corresponding to when δ = 0, x5 will still lie 2 inside as a consequence of (i). Thus δ cannot be less than zero. Lemma 2. Suppose X 4 = {x2 , x3 , x4 , x5 } is a set of four Euclidean plane points connected by a minimal T1 tree G consisting of the spanning edge x2 x3 and the full Q-component Q(x 3 , x4 , x5 ). Then the angle θ between x2 x3 and Q(x3 , x4 , x5 ) at x3 is at least 75◦ . Proof: The aim will be to show that a shorter tree than G exists by replacing one or both components with different components of shorter sum total length. Suppose x2 x3 and Q(x 3 , x4 , x5 ) meet at x3 at an angle of θ < 75◦ . Let s be the Steiner point of Q(x3 , x4 , x5 ) and o be the third point of the equilateral triangle 1ox4 x5 . Then |ox3 | = |x3 s|+|x4 s|+|x5 s| (Melzak, 1961). Now, as defined in Lemma l, let x20 , x40 , x50 and b be points such that x 20 , x3 , x40 , x50 form the corners of a square and x40 , x50 , b form the corners of an equilateral triangle so that b co-incides with o. Note that 6 bx3 x20 = 75◦ . Let C be a circular arc of radius |x3 b| centered at b, and define lU , lL , l 0 , C 0 , and δ as in Lemma 1. There are a number of situations to consider. (a) x 2 lies strictly inside the curve C and x2 b does not intersect x4 x5 . Let u be the intersection point of x 2 x3 and a line passing through x5 and o (figure 2). Clearly |x3 o| > |uo|

274

COLE

Figure 2.

The positioning of x2 .

so L G = |x2 x3 | + |Q(x3 , x4 , x5 )| > |x2 x3 | + |uo| = (|x2 x3 | + |ux5 |) + |x5 o| ≥ |Q(x 2 , x3 , x5 )| + |x4 x5 |. Thus G is not minimal as {Q(x2 , x3 , x5 ), x4 x5 } is shorter. Note that Q(x 2 , x3 , x5 ) may or may not be full. (b) x2 lies strictly inside the curve C and does intersect x4 x5 . In this case |Q(x3 , x4 , x5 )| = |x3 o| > |x2 o| = |Q(x2 , x4 , x5 )|. Therefore Q(x3 , x4 , x5 ) may be replaced by the shorter Q(x2 , x4 , x5 ) which again may or may not be full. (c) x2 lies on or outside the curve C. Note that x2 must lie strictly below the line lL else θ ≥ 75◦ . If x5 lies inside the curve C 0 then x2 x3 may be replaced by the shorter x2 x5 . This will be apparent as x5 will strictly be contained in the circular arc of radius x2 x3 centered at x2 . Now suppose x5 does not lie inside C 0 . If δ < 0 then by Lemma 1, x4 must lie strictly below lU . Consider G 0 = {x4 x5 , Q(x2 , x3 , x4 )} (figure 3a). Let s 0 be the Steiner point of Q(x2 , x3 , x 4 ), 0 < β = 6 x20 , x2 , x3 , β < γ 00 = 6 x20 , x2 , s 0 and assume ρ 0 L G /L G 0 ≤ 1. Move x2 toward x20 such that x20 x2 decreases at a rate of −1. The L G = −cos β < −cos γ 00 = L˙ G 0 < 0 so L˙ G / L˙ G 0 > 1 and Dρ 0 (v) < 0. Thus the ratio ρ 0 will decrease. Similarly if α = 6 s, x5 , x4 then move x5 toward s so that L˙ G = −1 < − cos α = L˙ 0G < 0 to again give L˙ G / L˙ G 0 > 1 and Dρ 0 (v) < 0. Note too that as b is fixed, o will move along l 0 toward x3 and δ will increase. When x2 = x20 and δ = 0, x3 and x2 lie on lU and lL respectively and x4 and x5 both lie between lU and lL . Note here that x5 may or may not now lie inside C 00 . Let w2 , w3 , x4 , x5 be the four points of a rectangle such that w3 lies on l 0 . (figure 3b) and note that as x 4 lies strictly below lU , w3 6= x3 . Move x 3 toward w3 along l 0 and x2 toward w2 at such rates so that x2 x3 is always perpendicular to lU and lL . Let ∅ = 6 w3 , x3 , s 0 and ω = 6 w2 , x2 , x3 . Then L˙ G = −1 − cos 75◦ − sin 75◦ · cot ω, and L˙ G 0 = −cos ∅ − sin 75◦ · cosec ω · cos(ω − ∅ + 15◦ ). Consider f (ω, ∅) = − L˙ G + L G 0 . Then ½

(cos ω · cos(ω − ∅ + 15◦ )) f (ω, ∅) = 1 + cos 75 − cos ∅ + sin 75 · sin ω ◦

◦

¾

275

PLANE MINIMAL T1 TREES

(a)

(b) Figure 3.

Regular point movement toward rectangular configuration.

and δ f (ω, ∅)/δω = −sin 75◦ ·

½

(1 − cos(15◦ − ∅)) sin2 ω

¾ ≤0

for 0 < ω ≤ 90◦ . Thus f (ω, ∅) ≥ f (90, ∅) = 1 + cos 75◦ − cos ∅ − sin 75◦ · cos(105◦ − ∅). The unique minimum to this equation, for 0◦ < ∅ < 60◦ occurs when ∅ = 51.206..◦ So f (ω, ∅) ≥ f (90◦ , 51.206..) = 0.0617339... > 0 giving L˙ G / L˙ G 0 > 1 and a decreasing ρ 0 . When w2 = x2 and w3 = x3 , L G and L G 0 may be calculated directly and both have the same value. Therefore a contradiction arises as L G cannot be shorter than L G 0 . If δ ≥ 0 then x5 must lie above lL else δ < 0 or x5 lies inside C 0 . Consider G 0 = {x 4 x5 , Q(x2 , x3 , x5 )} and assume ρ 0 = L G /L G 0 ≤ 1. Let s 0 be the Steiner point of Q(x2 , x3 ,

276

COLE

(a)

(b) Figure 4.

Defined collection of 6 T1 trees.

x5 ). It is now possible to follow a similar procedure as was used in the previous situation 2 when δ < 0 to arrive at the same contradiction that L G cannot be shorter than L G 0 . Definition 1. Suppose X 5 = {x1 , x2 , x3 , x4 , x5 }, a collection of 5 Euclidean plane points, is interconnected by a T1 tree G consisting of two full Q-components Q(x1 , x2 , x3 ) and Q(x 3 , x4 , x5 ) with Steiner points s1 and s2 respectively (figure 4a). Then define M = {A, B, C, D, E, F} to be the set of six T1 trees (figure 4b) as follows. A B C D E F

= {x1 x2 , Q(x2 , x3 , x4 ), x4 x5 } = {x1 x2 , Q(x2 , x3 , x5 ), x4 x5 } = {x1 x2 , Q(x1 , x3 , x4 ), x4 x5 } = {x1 x2 , Q(x1 , x3 , x5 ), x4 x5 } = {Q(x1 , x2 , x5 ), Q(x3 , x4 , x5 )} = {Q(x1 , x2 , x3 ), Q(x1 , x4 , x5 )}

Definition 2. Suppose X 5 = {x1 , x2 , x3 , x4 , x5 }, a collection of five Euclidean plane points, is interconnected by a T1 tree G consisting of two full Q-components Q(x1 , x2 , x3 ) and

PLANE MINIMAL T1 TREES

277

Q(x 3 , x4 , x5 ), with Steiner points S1 and S2 respectively. Define 1 to be the configuration space consisting of the six non negative edge lengths of G. i.e. 1 = {s1 x1 , s1 x2 , s1 x3 , s2 x3 , s2 x4 , s2 x5 } such that the sum of the lengths is equal to 1 and the angle between s1 x3 and s2 x3 is fixed and is at most 75◦ . Lemma 3. The length of any T 1 tree with respect to 1 is a convex function. Proof: The general result is proved by Du et al. (1991). (As all the angles and the topology of G are fixed, a point of 1 ⊂ R 5 will determine the configuration of the regular points. The length of any component of a T1 network interconnecting G can then be written as a vector sum and its length shown to be a convex function.) 2 Lemma 4. Suppose X 5 = {x1 , x2 , x3 , x4 , x5 } is a collection of five Euclidean plane points lying in some configuration such that (1) The T1 tree G (with length L G ) interconnecting X 5 consisting of two full Q-components Q(x1 , x2 , x3 ) and Q(x3 , x4 , x5 ) exists and is minimal; (2) The angle θ between the two edges s1 x3 and s2 x3 is strictly less than 75◦ . Suppose the maximum value of L G /L G 0 for all G 0 ∈ M at the configuration is ρ ∗ . Then there exists another configuration of X 5 such that G, consisting of the two full Q-components Q(x1 , x2 , x3 ) and Q(x3 , x4 , x5 ), exists, θ = 75◦ , and L G /L G 0 ≤ ρ ∗ . Proof: As G is assumed to be minimal at the initial configuration, ρ ∗ ≤ 1. Note that if a line x3 x1 intersects x5 s2 then G cannot be minimal as Q(x1 , x2 , x3 ) may be replaced by a shorter Q(x1 , x2 , x5 ) giving L G /L G 0 > 1 with G 0 = E ∈ M. Similarly if a line x3 x5 intersects s1 x1 then G cannot be minimal as Q(x3 , x4 , x5 ) may be replaced by a shorter Q(x1 , x4 , x5 ) giving L G /L G 0 > 1 with G 0 = F ∈ M. Thus suppose x3 x1 does not intersect x5 s2 and x3 x5 does not intersect s1 x1 . L G remains constant if Q(x1 , x2 , x3 ) is pivoted about x3 to increase θ and L G 0 does not decrease for any G 0 ∈ M. Thus L G /L G 0 will decrease for any G 0 ∈ M and so L G /L G 0 ≤ ρ ∗ for any 2 G 0 ∈ M. Remark. If L G 0 remains constant for some G 0 ∈ M when θ is increased, then L G /L G 0 < 1. This can be seen for each G 0 ∈ M. For example, suppose G 0 = A ∈ M. If Q(x2 , x3 , x4 ) is full then L G 0 must strictly increase. If Q(x2 , x3 , x4 ) = {x2 x3 , x3 x4 } then L G 0 remains constant. However in this situation it is obvious that L G /L G 0 < 1. Note that Q(x2 , x3 , x4 ) cannot be {x 2 x3 , x2 x4 } or {x3 x4 , x2 x4 }. Thus, by similar consideration of all G 0 ∈ M, it will be clear that when θ = 75◦ , L G /L G 0 < 1 for all G 0 ∈ M. Proof of Theorem 1: Consider two edges of T meeting at a common vertex with the angle between them strictly less than 75◦ . By definition each edge must either be a spanning edge or belong to some full Q-component. Let the two components be denoted by G. The proof will aim to show that a shorter network may be obtained by removing one or both components of G and by replacing them with different components of shorter sum length. There are 3 cases to consider. 2

278

COLE

First Case. G consists of two spanning edges. Clearly the edges may be replaced by a full Q-component of strictly shorter length. Second Case. G consists of one spanning edge and one full Q-component. By Lemma 2 there exist components of strictly shorter sum length which may be used as replacements. Third Case. G consists of two full Q-components. In this case, the proof follows the ideas of Du and Hwang (1992). Without loss of generality suppose G interconnects X 5 = {x1 , x2 , x3 , x4 , x5 } and G consists of the two Q-components Q(x1 , x2 , x3 ) and Q(x3 , x4 , x5 ) with the angle θ between s1 x3 and s2 x3 (s1 , s2 the Steiner points of Q(x1 , x2 , x3 ) and Q(x3 , x4 , x5 ) respectively) at x3 strictly less than 75◦ . Note that as T is minimal G must also be minimal. It is now only necessary to restrict attention to G. Consider G 0 ∈ M. Then L G /L G 0 ≤ 1 and by the Remark following Lemma 4 a minimum value of L G /L G 0 strictly less than 1 for all G 0 ∈ M will occur for some configuration of X 5 when θ = 75◦ . Consider the configuration space 1 as defined in Definition 2 and set θ = 75◦ . Then there exists some interior point po ∈ 1 such that G is a minimal T1 tree with |x3 s1 | ≥ |s2 x3 | > 0 (figure 5b).

(a)

(b) Figure 5.

a) Square configuration of regular points, b) |x3 s1 | ≥ |s2 x3 | > 0.

279

PLANE MINIMAL T1 TREES

Let p1 correspond to a configuration of X 5 such that |s2 x4 | = |s2 x5 | = 0 |s2 x3 | = ¡ |x3 x4 | 1+

√

√2 ( 3

1

¢,

2 + sin 15◦ )

|s1 x2 | (2 sin 15◦ ) = ¡√ ¡ √ ¢¢ , |x3 x4 | 3 1 + √23 ( 2 + sin 15◦ ) and |s1 x1 | |s1 x3 | = = ¡√ ¡ |x3 x4 | |x3 x4 | 3 1+

√ 2 √ ◦ ¢¢ 2 √ ( 2 sin 15 ) 3

i.e. when s2 = x4 = x5 and x1 , x2 , x3 , and x4 (=x5 ) lie as the corners of a square (figure 5a). Note that for any G 0 ∈ M, L G /L G 0 = 1 at p1 . Now consider the path (1 − λ) p1 + λpo ∈ 1 for λ ≥ 0. Note that since |s2 x4 | = |s2 x5 | = 0 at p1 but |s2 x4 | > 0 and |s2 x5 | > 0 at po , some edge of G must decrease at a constant rate as λ increases. Let r = |s1 x3 |/|s2 x3 |. Then r (λ) is an increasing function. (At p1 , r = sin 45◦ /sin 60◦ < 1, and at po , r ≥ 1). Thus there will exist some λ > 1 such that one of the following occurs. (a) (b) (c) (d)

G intersects itself. |s1 x3 | · 2 cos 75◦ ≤ |s2 x3 | ≤ |s1 x3 | and at least one Q-component of G is not full. |s2 x3 | = |s1 x3 | · 2 cos 75◦ and both Q-components of G are full. |s1 s3 | · 2 cos 75◦ > |s2 x3 |

Let p10 ∈ 1 correspond to the smallest λ > 1 for which one of the above occurs. Then to prove Theorem 1 it is necessary to find a T1 tree G 0 6= G such that L G /L G 0 ≥ 1 at both p1 and p10 ∈ 1. It will then follow that L G /L G 0 ≥ 1 at po by the convexity of L G 0 and hence a contradiction that G is minimal. Each situation is considered separately. (a) G intersects itself. There are two possibilities. If s2 x5 intersects s1 x1 (figure 6a) then choose G 0 = {Q(x1 , x2 , x5 ), Q(x3 , x4 , x5 )} = E ∈ M. Since |Q(x1 , x2 , x5 )| ≤ |Q(x1 , x2 , x3 )| at p10 , L G /L G 0 ≥ 1, at both p1 and p10 . Thus L G /L G 0 ≥ 1 at po by the convexity of G 0 and so contradicting the minimality of G. If s1 x1 intersects s2 x5 (figure 6b) then choose G 0 = {Q(x1 , x2 , x3 ), Q(x1 , x4 , x5 )} = F ∈ M and a similar argument follows. (b) |s1 x3 | · 2 cos 75◦ ≤ |s2 x3 | ≤ |s1 x3 | and at least one Q-component of G is not full. In this case p10 lies on the boundary of 1. Assume G does not intersect itself. Note that both x4 s2 and x5 x2 have non zero length at p10 , and |s1 x3 | ≥ |x3 s2 | > 0 also at p10 . Thus only x 1 s1 or x2 s1 can have zero length at p10 .

280

COLE

(a) Figure 6.

(b)

a) s2 x5 intersecting s1 x1 , b) s1 x1 intersecting s2 x5 .

The problem can now be considered as a geometric problem. Let x40 , x50 be points such that s1 , x3 , x40 , x50 form the corners of a square. Also let o0 be the third point of the equilateral triangle 1o0 s1 x3 , C 0 be the circular arc of radius |s1 x3 | at S1 , o be the third point of the equilateral triangle 1ox4 x5 , q be a line passing through o0 and the midpoint of x40 x50 , q 0 be a line passing through o0 and S1 , lU be a line passing through x3 and x40 , lL . be a line passing through s1 x50 , and define δ be the angle measured clockwise at x4 from a line parallel with x40 x50 to x4 x5 . Note that if |s2 x3 | = |s1 x3 | · 2 cos 75◦ then s2 will lie on C 0 (figure 7). There are two situations to consider. (b.1) If x5 lies inside C 0 then |s1 x5 | ≤ |s1 x3 | and |Q(x1 , x2 , x5 )| ≤ |Q(x1 , x2 , x3 )|. Thus G 0 can be chosen to be E ∈ M to give L G /L G 0 ≥ 1 and a contradiction that G is minimal at po . (b.2) If x5 lies outside C 0 then there are a number of situations to consider.

Figure 7.

The location of x5 .

281

PLANE MINIMAL T1 TREES

(i) x 4 lies below lU and x5 lies above lL . If |x1 s1 | = 0 and δ ≤ 0 then choose G 0 to be {x1 x2 , Q(x1 , x3 , x4 ), x4 x5 } = C ∈ M. If x4 lies strictly below lU then follow similarly the procedure used in Lemma 2 to show that |s1 x3 | + |Q(x3 , x4 , x5 )| ≥ |x4 x5 | + |Q(x1 , x3 , x4 )| to give the contradiction. If x4 lies lU then it may be shown again that |s1 x3 | + |Q(x3 , x4 , x5 )| ≥ |x4 x5 | + |Q(x 1 , x3 , x4 )| by decreasing the edges s1 x3 = x1 x3 at s1 = x1 or decreasing s2 x5 at x5 until x1 , x3 , x4 , x5 lie as the corners of a rectangle from which L G = L G 0 to give the contradiction of the minimality of G. Similarly if |x2 s1 | = 0 and δ ≤ 0 then choose G 0 to be {x1 x2 , Q(x2 , x3 , x4 ), x4 x5 } = A ∈ M. |x1 s1 | = 0 and δ > 0 then choose G 0 to be {x1 , x2 , Q(x1 , x3 , x5 ), x4 x5 } = D ∈ M. |x 2 s1 | = 0 and δ > 0 then choose G 0 to be {x1 x2 , Q(x2 , x3 , x5 ), x4 x5 } = B ∈ M. (ii) x4 lies above lU and x5 lies above lL . In this situation δ > 0 so if |x1 s1 | = 0 choose G 0 to be D ∈ M, and if |x2 s1 | = 0 choose G 0 to be B ∈ M and proceed as in (i). (iii) x4 lies below lU and x5 lies below lL . If δ ≤ 0 and |x1 s1 | = 0 choose G 0 to be C ∈ M, and if δ ≤ 0 and |x2 s1 | = 0 choose G 0 to be A ∈ M. Move x5 toward s2 to decrease L G /L G 0 until δ = 0. If x5 lies above lL when δ = 0 then proceed as in Lemma 2 to obtain the contradiction. If x5 lies below lL when δ = 0 then it is not possible to proceed as in Lemma 2. It will therefore be necessary to re-examine the problem. Note here that o lies below q. This situation will now be examined in (iv). If δ > 0 then o must lie below q. This situation will also now be examined in (iv). (iv) x4 lies above lU and x5 lies below lL . In this situation o lies below q so |x3 o| ≥ |s1 o|. First suppose |x1 s1 | = 0, (figure 8a). If s1 o intersects x4 x5 then |Q(x1 , x4 , x5 )| ≤ |Q(x3 , x4 , x5 )| so choose G 0 to be F ∈ M. If s1 o does not intersect x4 x5 then note that o must also lie below lL . Let u be the point of intersection of s1 x3 and a line passing through ox5 . Then clearly |x3 o| > |uo| ≥ |x1 x5 |+

(a) Figure 8.

a) |x1 s1 | = 0, b) |x2 s1 | = 0.

(b)

282

COLE

Figure 9.

x1 o does not intersect x4 x5 .

|x5 o|. Thus Q(x3 , x4 , x5 ) may again be replaced by the shorter Q(x1 , x4 , x5 ) and G 0 may be chosen to be F ∈ M. Next, suppose |x2 s1 | = 0, (figure 8b). If x1 o intersects x4 x5 then |Q(x1 , x4 , x5 )| ≤ |s1 o| ≤ |Q(x3 , x4 , x5 )| by geometric considerations so G 0 may again be chosen to be F ∈ M. Now suppose x1 o does not intersect x4 x5 . Define d to be the distance from s1 to the intersection point between q 0 and a line passing through s2 and x5 when |x3 s2 | = |x3 s1 |, (figure 9). If |x 1 s1 | ≥ d = (cos 52.5◦ /cos 67.5◦ ) · |x3 s1 | = (1.5907703...). |x3 s1 | (i.e. in this situation x5 must lie above q 0 .), then the shortest distance between x5 and x1 s1 is at most d · tan 30◦ .|x3 s1 |/(tan 30◦ + 1) = (0.5822623...). |x3 s1 | < |x3 s1 |. Thus |Q(x1 , x2 , x3 )| ≥ |Q(x1 , x2 , x5 )| so G 0 may be chosen to be E ∈ M. Now suppose x1 s1 < d. If x5 lies below q 0 then o must also lie below q 0 . Let u be the point of intersection of x3 s1 and a line through o and x5 . Then clearly |x3 o| > |uo| ≥ |s1 x5 | + |x5 o| ≥ |x1 x5 | + |x5 o|. Thus Q(x3 , x4 , x5 ) may again be replaced by the shorter Q(x1 , x4 , x5 ) and G 0 may be chosen to be F ∈ M. If x5 lies above q 0 then there are two situations. If |x1 x5 | ≤ |x3 s1 | then replace Q(x1 , x2 , x3 ) by the shorter Q(x1 , x2 , x5 ) and choose G 0 to be E ∈ M. If |x1 x5 | > |x3 s1 | then |x1 s1 | can be at most (d − |x3 s1 |) = (0.5907703...).|x3 s1 |. Note that the angle between x 1 x5 and q 0 at x1 is at most the angle that x50 x1 is with q 0 and is less than 90◦ , (figure 10). Let u 0 be the intersection point between x1 s1 and

PLANE MINIMAL T1 TREES

Figure 10.

283

The angle between x1 x5 and q 0 at x1 .

a line passing through o and x5 . Then the angle between u 0 o and q 0 is also less than 90◦ and |x3 o| > |u 0 o| = |u 0 x5 | + |x5 o| > |x1 x5 | + |x5 o|. Therefore Q(x3 , x4 , x5 ) may be replaced by the shorter Q(x1 , x4 , x5 ) and G 0 may be chosen to be F ∈ M. Similarly if u 0 is the intersection point of x3 s1 and a line passing through o and x5 then |x3 o| > |u 0 o| ≥ |s1 x5 | + |x5 o| ≥ |x1 x5 | + |x5 o| and G 0 may be chosen to be F ∈ M again. (c) |s2 x3 | = |s1 x3 | · 2 cos 75◦ and both Q-components of G are full. If x5 lies inside C 0 then |Q(x1 , x2 , x5 )| ≤ |Q(x1 , x2 , x3 )| so G 0 may be chosen to be E ∈ M. √ If x5 lies outside C 0 then as s2 lies on C 0 , x5 lies below lL and |s2 x2 | ≥ 2 · |s1 x3 |. Let w be the intersection point of q and a line passing through x3 and s2 , (figure √ 7). Then |x 3 o| = |Q(x3 , x4 , x5 )| = |s2 x3 | + |s2 x4 | + |s2 x5 | > (2 cos 75◦ + 2) · |s1 x3 | > |x 3 w|. Thus o must lie below q. The proof may now follow similarly to that of (b.iv). (d) |s1 x3 | · 2 cos 75◦ > |s2 x3 |. If |s1 x3 | · 2 cos 75◦ < |s2 x3 | at p0 then p10 can always be chosen to satisfy one of the conditions (a), (b), or (c) for some λ > 1. If at po , |s1 x3 | · 2 cos 75◦ ≥ |s2 x3 |, then it only needs to be shown that G cannot be minimal at p0 for θ ≤ 75◦ . Note that |s1 x1 | > 0. Thus if x 5 lies in or on C 0 then L G > L G 0 for G 0 = E ∈ M. If x5 lies outside C 0 then since s2 lies inside C 0 , x5 must lie below lL . Note also that as it only needs to be shown that G is not minimal at po there is now not the restriction of examining networks only from M. Thus it will be apparent that |x1 x5 | is strictly less than either |s1 x1 | or |s2 x5 |. If the former occurs then G is longer than {x2 x3 , Q(x3 , x4 , x5 ), x1 x5 }, and if the latter occurs then G is longer than {x1 x5 , Q(x1 , x2 x3 ), x3 x4 }.

284

COLE

This completes the proof of the third case. Thus since (T /G) ∪ G 0 is a T1 tree and L G 0 < L G , |(T /G) ∪ G 0 | < |T | and so T cannot be minimal. 2 Remark. Note that as the proof was by contradiction method it is clear that the result is best possible. i.e. a T1 network with any angle less than 75◦ cannot be minimal. References D.Z. Du, Y.J. Zhang, and Q. Feng, “On better heuristic for Eulidean Steiner minimum trees,” in Proc. of the 32nd Ann. Symp. on Foundations of Computer Science, 1991, pp. 431–439. D.Z. Du and F.K. Hwang, “A proof of Gilbert and Pollak’s conjecture on the Steiner ratio,” Algorithmica, vol. 7, pp. 121–135, 1992. Z.A. Melzak, “On the problem of Steiner,” Canad. Math. Bull., vol. 4, pp. 143–148, 1961. J.H. Rubinstein and D.A. Thomas, “The calculus of variations and the Steiner problem,” Ann. Oper. Res., vol. 33, pp. 481–499, 1991.