ON THE STEINER PROBLEM by ERNEST COCKAYNE M.A., (Oxon) 1965 H.Sc, McGill University, 1963. A THESIS SUBMITTED IN PARTIAL FULFILMENT OF THE REQUIREMENTS FOR THE DEGREE OF DOCTOR OF PHILOSOPHY in the Department of Mathematics We accept this thesis as conforming to the required standard. THE UNIVERSITY OF BRITISH COLUMBIA June, 1967 In p r e s e n t i n g t h i s t h e s i s in p a r t i a l f u l f i l m e n t of the requirements f o r an advanced degree at the U n i v e r s i t y of B r i t i s h Columbia, I agree t h a t the L i b r a r y s h a l l make i t f r e e l y a v a i l a b l e f o r r e f e r e n c e and Study. I f u r t h e r agree that p e r m i s s i o n f o r e x t e n s i v e copying of t h i s t h e s i s f o r s c h o l a r l y purposes may be granted by the Head of my Department or by h.i.-s r e p r e s e n t a t i v e s . It i s understood t h a t copying or p u b l i c a t i o n of t h i s t h e s i s f o r f i n a n c i a l gain s h a l l not be a l l o w e d w i t h o u t my w r i t t e n p e r m i s s i o n . Department of ^ A M i c ^ The U n i v e r s i t y of B r i t i s h Columbia Vancouver 8, Canada - i i -Thesis Supervisor: Dr. Z. A. Melzak» ABSTRACT The cla s s i c a l Steiner Problem may be stated: Given n points a in the Euclidean plane, to construct the shortest tree(s) 1 n (i . e . undirected, connected, c i r c u i t free graph(s)) whose vertices include a,,...a . 1 n The problem is generalised by considering sets in a metric 2 space rather than points in E and also by minimising a more general graph function than length, thus yielding a large class of network minimisation problems which have a wide variety of practical applications, The thesis is concerned with the following aspects of these problems. 1. Existence and uniqueness or m u l t i p l i c i t y of solutions. 2 . The structure of solutions and demonstration that minimising trees of various problems share common properties. 3. Solvability of problems by Euclidean constructions or by other geometrical methods. - i i i -TABLE OF CONTENTS page CHAPTER I Introduction 1 CHAPTER II Existence Theorem 5 2 CHAPTER I I I An Effective Algorithm for (S^) in E 8 2 CHAPTER IV (S ) for Sets in E 18 n CHAPTER V (S n) in Other Metric Spaces 1. Euclidean ra-space 21 3 2. A Surface in E 21 3. Plane Minkowski Metric Space 23 CHAPTER VI More Properties of (S 36 ncxp / BIBLIOGRAPHY 41 - iv -ACKNOWLEDGEMENTS I wish to express my warmest thanks to Dr. Z. A. Melzak both for his suggestion of the topic and his generous encouragement and assistance during the preparation of this thesis. I am also indebted to Dr. V i r g i n i a Walsh of the University of V i c t o r i a for her constructive c r i t i c i s m of the f i r s t draft of the material and to Mrs. Mae Peters for her excellent typing of the manuscript. The f i n a n c i a l support of the Canadian National Research Council and the University of B r i t i s h Columbia is gratefully acknowledged. - 1 -I INTRODUCTION Our starting point i s the well known elementary problem: 2 (S^) Given 3 distinct points aya.^,a^ in E to find the point p which minimises the sum of distances pa^ + pa^ + pa^. If triangle a^^a-j n a s an angle > 120°, then p is i t s vertex, otherwise p is the unique point at which the sides of the triangle subtend angles of 120° and is called the Steiner point of the triangle. (S^) may be generalised in many ways. For example 2 (P ) Given n distinct points a.,...,a in E to find the point p which n r 1' ' n n minimises the function S pa.. i=l 1 (P 3) and (S 3) are identical. Let b^,...,b^ be any set of distinct points in the plane. By a tree U on the vertices b1,...b„ we mean any set consisting of (V\ I N some of the J closed straight segments b^b^ with the property that any two vertices can be joined by a sequence of segments belonging to U in one and only one way. A segment b^b^ in U is called a branch of U, the length L(U) of U is the sum of the lengths of i t s branches and (b^J i s the set of a l l vertices sending branches to the vertex b^. The valency of b^, written w(b^), is the number of vertices in {b^J. We can now formulate further generalisations of (S^): (S ) Given n distinct points a,,...,a in the plane (n > 3), to construct n' I n r x _ ,, the shortest tree(s) whose vertices include a^,...,an and any set of k additional plane points s^,...,s^ ( k > 0). (S^p^) Given three non-negative real numbers a,8,7 and n distinct points a^,...,an in the plane, to find an integer k and k additional points s ^ , . . . , S j t , and to construct the tree(s) U on the vertices a,,...,a , s,,,..,8, so as to minimise the sum 1 n 1 k n k T - L(U) + a L w(a.) + 8 E w(s,)+ 7k. i-1 1 i=l 1 - 2 -If a = B = 7 = 0 , (S^^,) reduces to ( S ^ ) . Suppose now that p = 0 and a > 7 where j i s s u f f i c i e n t l y large. T w i l l then be smallest when each w(a^) has i t s minimum value 1 so that as few extra vertices as possible are adjoined. However, since a tree is connected, w(a^) = 1 for each i implies that k > 1 . I t follows, therefore, that when p = 0 and for suitable a, 7, the minimising trees of (snap^,) w i l l be precisely the minimum length trees among those having w(a^) = 1 for each i and k - 1 i.e. (S ) reduces to (P ). A similar argument shows that i f nCtp7 n max ((3,7) » 1 and a = 0 , then isna^y) reduces to ( C ^ ) To connect n distinct given points in the plane by the shortest trees(8) whose vertices are these n points. ( C q ) is not a generalisation of ( S ^ ) and has the important property of being discrete i.e. the length is to be minimised over a f i n i t e set of trees, while (S ), (P ) and (S „,„ ) are not discrete, since the ' x n " n' v nap7' ' co-ordinates of the extra vertices s^,...,s^ are continuously varying unknowns. (*>nap^) and i t s special cases may be extended s t i l l further by replacing the n given ppints a^,...,an with n disjoint plane, compact, connected sets A^,...,An« The definition of a tree given above is s t i l l v a l id with the following minor modifications. A vertex i s a set and by the "segment" B^Bj w e taean a line of shortest distance joining the sets B^ and . Such extremals certainly exist by a standard continuity and compactness argument. The f i n a l generalisation is to change the metric space in the formulation. In the definition of a tree "segment" is replaced by "geodesic". For example we may consider identical problems in E m, on the surface of a sphere in or in Minkowski metric spaces Mm. We formulate our most general problem: ^ S nap7^ L e t M 1 , 6 a m e t r i c 8 P a c e with metric >^ which has the following properties: - 3 -1. M is f i n i t e l y compact. 2. There exists a geodesic in M joining each two points of M. 3. For a l l a, b € M, p (a,b) is equal to the length of a geodesic joining a and b. Given three non negative real numbers OL, 8,7 and n dis j o i n t , compact, connected sets A^,...,An in M, to find an integer k and k additional points s^,...,s^ € M, and to construct the tree 0 on the vertices A,,....A , s 1,....s. so as to minimise the sum 1 n 1 k n k T = L(U) + a S w(A.) + B Z w(s ) + 7k. i=l 1 i=l J-Conditions (2) and (3) give meaning to the idea of a minimum length tree in the space M while (1) w i l l be used to demonstrate the existence of such a tree. This class of problems offers a wide variety of practical applications. The problems of joining geographical points, metropolitan areas, a set of lakes or sets of e l e c t r i c a l terminals by minimum length systems of roads, railways, canals or connecting wire respectively are 3 3 a l l examples of (S n) for points or sets in some surface in E or in E i t s e l f . The particular Minkowski metric space which has distance function d(z^,z^) = l x i " x 2 | + |y^-y2| is called the Manhattan metric. If there are n stores in a network of c i t y blocks to be supplied by separate trips in rotation from a central supply depot, the optimal position for the depot is a solution of (I"n) in this Manhattan metric space. This has further application in some printed c i r c u i t designs where terminals may be joined only by wires running in two perpendicular directions. F i n a l l y suppose we wish to minimise the cost of a communications network joining areas A^ ,...A in which there is a cost per unit length and also costs per terminal depending on the number of connections at the terminal, then the minimum cost networks w i l l be solutions of (S^^ Q v) in some metric space and for some a,8,7. - 4 -The problem (S,) dates back to Fermat and the generalisation 2 ( S q ) in E is called the Steiner problem, and appears in the collected works of Steiner. In [1] there i s a summary of the knowledge of (S^) in 1941 and some interesting solutions, found by stretching soap films between pegs and glass plates, are exhibited. Recently due to the diverse applications, there has been renewed interest in these problems. 2 Princ i p a l l y Z.A. Melzak [2] showed that (S^) in E is solvable by a f i n i t e number of Euclidean constructions ( i . e . ruler-compass constructions in the c l a s s i c a l sense) and posed ( S ^ ^ ) . R.C. Prim [3] has given an algorithm for solving [G^]. Other results include a solution of (S n) for n points i n Manhattan metric space by Hanan [4], and a uniqueness theorem for (P^) by Palermo [5]. Other minor references are [6] and [7]. The Thesis is concerned with the following aspects of these problems: (a) M u l t i p l i c i t y or uniqueness of solution (b) f e a s i b i l i t y of constructing a l l solutions by Euclidean constructions or possibly by wider geometrical algorithms, (c) the structure of minimising trees and demonstration that minimising trees of various problems share common structures. The f i r s t section proves the existence of a l l minimum points and minimising trees mentioned in the thesis. We then consider the 2 problem (S^) for n points in E giving another proof of the theorem that i t is solvable by a f i n i t e number of Euclidean constructions. The proof clearly explains the algorithm involved and exhibits the structure of minimising trees. The methods used here are then generalised to solve 2 (S ) for n sets i n E . We continue with a demonstration that solutions n 3 of (S^) in other spaces namely E , a general surface in E and Minkowski metric spaces share common properties. The f i n a l section discusses the problem (S ), showing that in Minkowski space i t has a f i n i t e number r % nap7 2 of solutions and that in E i t is not in general solvable by Euclidean constrictions. - 5 -I I - EXISTENCE THEOREM In this section we prove that minimising trees (points) exist for a l l problems mentioned in the thesis. A preliminary result shows that (S Q ap^) is equivalent to a f i n i t e number of minimum length problems. Let A^,...,A^ be n d i s j o i n t , compact, connected sets in a metric space M having the three properties l i s t e d in section 1. Definition. U is a u-tree on A = {A,,...,A } i f U is a tree whose 1 n vertices are A,,...,A and the points s.,...,s. which s a t i s f i e s : I n l k ( i ) w( S i) > 3 , i = l,...,k. ( i i ) 0 < k < n-2. Lemma. If a solution of ( s n ap^) exists, i t is a u-tree on A. Proof. We shall c a l l the extra vertices s ,...,8^, "s-points". w(s i) > 2 for each i , otherwise we could decrease T by deleting s^. Now suppose w(s^) = 2 for some i . Then the tree formed by replacing s^x, s^y, the two branches joining s^, by the single branch xy, has a smaller value of T. Hence ( i ) . The number of branches of 0 leading to s-points is > 3k/2 from ( i ) , the connectivity of U assures us that the number of branches from the A-sets is > n/2 and a tree with n+k vertices has n+k-1 branches. Therefore (n+3k)/2 < n+k-l,.from which we deduce ( i i ) . Definition. By the association of a u-tree U on A, we mean the integer k and the sets (A^ and {s^} ( i = l,...,n , j = l , . . . , k ) . Theorem 1. The problemfs _ ) is reducible to a f i n i t e number of minimum r V naB7^ length problems. Proof. The relation "has the same association as" on the set of a l l u-trees on A is an equivalence relation. We show that the number of equivalence classes i s f i n i t e . Suppose there are k additional vertices. Then we have n+k vertices on which to construct a tree. i.e. n+k-1 pairs of vertices to be joined, must be selected from the possible ( 2 ) P a i r s > - 6 -Thus the number of associations with k extra vertices is not greater than n " 2 , and the total number of associations is not greater than Z g(n,k) k=0 and hence is f i n i t e . Let the equivalence classes be C^,...,CN and let C be any one of these classes. The tree(s) which minimise T in C are precisely the tree(s) of minimum length of C ( i f one exists), since the association common to a l l the tree(s) of G fixes the other three terms of T i.e. for a l l U e C n k a Jj^ + p ^ w ( S j ) + 7k is constant. The minimising trees of (S ) are a subset of the trees belonging to n0£p7 C^,...,CN by the Lemma. Therefore, each minimising tree of (S n ap^) is a solution to one of the following N minimum length problems: (1) For i - 1,...,N to construct the tree(s) U € which minimise L(U). Theorem 2. Let C 6 (C^,...,C N). There exists a tree of minimum length in C. Proof. The association of trees in C stipulates which of the pairs s^Aj , s^Sj > w i l l be joined by geodesies as branches of trees in C. We exclude the case k = 0 for which the theorem is obvious. Let (A.,, A_,„,...,A5, ) = (A : A £ A and s,A^ is a branch of trees in C} 1 i l ' i 2 ' iX^ 1 t t i t 1 and let R^ jR^ , sets of unordered pairs of integers be defined as follows: R^ = ( ( i , j ) : 8 i s j i s a branch of trees in c}. R2 = {(i,J) : a t a j i s a branch of trees in C). - 7 -Then the length of a tree in C i s k X i f(s ,...,s ) = Z Z p (s ,A ) + Z p(s ,s ) 1 k i = L j=l f 1 i j (i,j)£R I 1 J + Z p(A ,A ) . (i,J)€R 2 r i J Suppose L i s the length of the shortest tree with vertices A^,...,An only. Let Z = (z : z e M and min p (z,A ) < LJ . i I i Then every s-point of a tree of shortest length in C ( i f one exists) is in Z, for otherwise the length of the tree would necessarily be greater than L. Thus i f [s^,...,s^} is a set of s-points of a minimum length tree in C, then [s 1 /...,s ) is an element of the cartesian k I K product Z . Now sihceZ is closed and bounded and M is f i n i t e l y compact, Z is compact implying by the Tychonoff Theorem that Z is compact. But k k ICS- • » • » i s. ) is continuous on Z and so has a minimum value on Z . 1 k Hence the theorem. Corollary. There exist minimising trees of (.sna^y) *-n M« F o r (snapy) is equivalent to the f i n i t e set (1) of minimum length problems (Theorem 1.) each of which by the theorem has a solution. - 8 -I I I - AH EFFECTIVE ALGORITHM FOR (S ) IK E 2. n-i We begin by stating elementary constructions of the solution of (S^) which was given in the introduction. These constructions are of fundamental importance in the development of the algorithm for (S^) both for points in the plane and for n sets in the plane which w i l l be discussed in the next chapter. Let a^,a^,a^ be the vertices of a plane triangle T with no angle > 120 and ai2 a23 a31 b e t n e three third vertices of the equilateral triangles b u i l t outward on the sides of T (with obvious notation). Then p, the minimum point of (S^), l i e s at the unique point of intersection inside T of the circumscribing circles of the equilateral triangles. Again, i f p' is the intersection of the line a 1 2 a 3 with the c i r c l e through a j a 2 a i 2 > each side of T subtends 120° at p' which therefore coincides with p. It follows that each of the lines a^a^ f a^^a^ , a^^a^ passes through p giving a third method of construction. a. Fig. 1. - 9 -Using the notation as in f i g . 1. by the sine law a-jP sin a * 2P sin(60-a) a 1 2P sin(60+a) . . a l P + a 2p = a 1 2p sin a + sin (60-Os) sin (60+3) = a 1 2p The addition of a^ p to each side gives a12 a3 = a l P + a 2 P + a 3 P * Thus each of the three lengths a^ 2 a3> a j i a 2 ' a 2 3 a l e 1 u a l 8 t i i e minimum value of the function a^x + a 2x + a^x . We remark that i f T has an angle > 120 none of the above constructions w i l l produce a point inside T. Suppose A = {a^,... >a nJ is a set of n distinct points in the plane and that U, a minimising tree of (S ) for the set k, has extra vertices n Then P i . U i s non-self intersecting, i.e. two branches of U do not intersect except at an end point. w(s^) = 3 , i = l,...,k. P2. P3. P4. P5. w( aj) < 3 , j = I,...,n. 0 < k < n-2. Each s^ is the Steiner point of the triangle formed by (s^). These properties are given in [1]. We indicate the proofs for completeness. Suppose that two branches x ^ x 2 t X3 X4 °^ ^ intersect at x. Then one of the angles at x (say 2^ x^xx^) is less than 120 and U may be shortened by replacing the segments x^x, x^x by x^p, x^p, xp where p is the solution of (S^) for the triangle x^x^x. Hence P i . An identical argument proves that w(x) < 3 for a l l vertices x of U. Therefore U has the property P3 and ^ ( 8 ^ ) < 3 for each i . However w(s^) > 3 for otherwise there is no gain in introducing the additional vertex s^. Thus P2 is established and from this P5 is immediate. P4 is proved as in the Lemma on Page 5, - 10 -Definitions. A tree with vertices {a^, . . . , 8 ^ } and { s ^ . . .,8^) (from this point these w i l l be termed a-points and s-points respectively) has the property P4 i f k = n-2. V i s a subtree of a tree U i f and only i f ( i ) V is a tree and ( i i ) the set of geodesies of V is contained in the set of geodesies of U. A tree U i s an S-tree on A i f i t has properties PI, P2, P3, P4, P5. A tree D i s an S-tree on A i f i t has properties P i , P2, P3, P4, P5. * — A tree U is an S -tree on A i f i t has properties P2, P3, P4, P5. The f i n i t e set {A^A^ ... ,At,R], (t > 0) is a Division of the set A i f and only i f 1. Each A± C A , R C A . 2. R r i A i = 0 , i = l , . . . , t . 3. No a. can be an element of more than 3 of the sets A.. 4. Each has 3 or more elements. 5. A x U A 2 U ... U A t U R « A . Lemma 1. If U is any S-tree on A then for some division Qt~ (A^^A^,• • • ,A( of A there exist S-subtrees of U on A. for i = l , . . . , t . l ' Proof. I f 0 contains no. s-point, the required division is {A}. If S, the set of s-points of U is non-empty, we define the relation "o" on S as follows. s o s i f f the sequence of segments of U joining s to s contains no i j 1 J a-point of U. The relation is an equivalence relation and therefore partitions S into mutually exclusive and exhaustive sets S^ ,...,S (t > 0 ). Define A. = fa . : a. € {s. 1 for some s, e S. } , i = 1,....t and t R = A - U A.. The set f A, ,A„,...,AJ.,R) is a division of A. I t remains 1=1 i 1 1 2 ' t' to show that there Is an ^-subtree of U on each A^. Let be the subtree of U whose vertex set is A^ U S^ , i = 1,..., t . (This is certainly a subtree of U by construction). has the properties P1,P2,P3 and P5. We prove P4. Let A i contain p points, q points and further suppose that S^ contains n^,n2,n^ s-points which directly join 1,2 and 3 other s-points respectively. Then - 11 -(2) n x + n 2 + n 3 = q . The number of branches of connecting s-points i s (n^ + 2n 2 + 3n 3)/2. But by the defining property of this number is q-1. Hence (3) iij, + 2n 2 + 3n 3 = 2(q-l). The number of branches of connecting an a-point to an s-point i s 2n^ + n 2 since the valency of each s-point is 3. Hence (4) 2n x + n 2 = p . From equations (2) (3) and (4) we deduce q = p-2. Therefore U satisfies P4 and is an S-subtree of U. Hence the Lemma. Incidentally one can also prove n^ - n 3 = 2 from (2) (3) and (4) which implies that n^ > 2. We note that the non-selfintersection property is not involved in the establishment of these equations and state that an * S -tree on a set A has at least two s-points which directly join exactly one other s-point and two a-points. This fact w i l l be used i n the next Lemma. We c a l l the subtrees ( i = l , . . . , t ) the Components of U and suggest that the components of a minimising tree U may be considered as s t a b i l i t y sets for U in the following sense. I f one a-point a^ i s perturbed by a su f f i c i e n t l y small amount, there is a minimising tree D' for the new set of n a-points which is identical to U except for a small perturbation of the components to which a^ belongs. I f p,q are points in the plane we shall denote by (pq) and (qp) the third vertices of the equilateral triangle on pq as base, (pq) being the point to the l e f t of p looking from p along pq. The construction we now describe, a direct consequence of the solution of (S 3), is crucial to the proof. Let U be an S-tree on A = fa^,...,a n) with s-points B^,...,a^ then there exists (see note following Lemma 1.) an s-point say s 1 which is directly connected - 12 -to two a-points say a^ and a^ and a third vertex x. In fact a portion of U appears as in f i g . 2. Fig. 2. Since is the Steiner point of {B^}, the line xs^ produced passes through (*2a^) a n d t n e t r e e o n A ' " ( ( a 2 a i ) > a3'** , , an^ w i t n 8 ~ P o i n t 8 s^,...,*^ formed from U by replacing the branches a^8-^ > a 2 e i ' s i x the single branch (a2«^)x is an S -tree on A' (the non-selfintersection property may have been contradicted). Further a^s^ + *2ei + 8 ^ x = ( a 2 a l ^ x therefore U,U' have equal lengths. The important point is that (a^a^) is constructed from the original a-points only. We call the above the "Equilateral construction." We next define the term "Association" of an S-tree on a set A. From U, we form a tree U' and set A' as above. The construction is repeated forming a new tree U" and set A", U'" and A'" etc. until the set A^r^ contains only two points. (Actually r • the number of (r) s-points in the original tr^e U). The two points of Av ' can be expressed -13 -in terms of the original a-points of U and the equilateral triangle (r) bracketing notation defined above. This representation of A we call an "Association" of the tree U and the line joining the two points (r) of A we ca l l an "axis" of U. We give a simple example below. We note the following: (i) The process is always possible since at every stage (k) * (k) the tree U i s an S -tree on A and hence has an s-point which directly joins two a-points^ (in fact at least 2 such s-points by the note following Lemma 1), (i i ) It follows from (i) that every S-tree on A has an association and an axis (certainly not a unique association.) ( i i i ) At each stage length is preserved, i.e. The length L ( U ) = length of an axis of U. (iv) No two S-trees on A have a common association. Example. In Fig. 3jU is an S-tree on A = {1,2,3,4,5} with s-points (M)('3)j Fig. 3. - 14 -We "pair" the points 1 and 3 giving A1 = {(13), 2, 4, 5} and U' with branches(13)s 3,s 35,s 2s 3,2s 2,4s 2. Next we pair 4 and 2 A" = {(13),(42),5} JU" has branches (42)s 3,(13)s 3,s 35. F i n a l l y we pair (13) and (42) A"' = f((42)(13)) , 5]JU"' has branch ((42)(13))5. The underlined portion i.e. A"' without the set parentheses is an association of U. The length of U is the length of the branch of U"'. Lemma 2. I f i t is known that U, an S-tree on A has a certain association a, we can construct U by a f i n i t e number of Euclidean constructions. Proof The Lemma is true for n = 3. Assume i t is true for n = N and let AJJ+^ = {a^,... >ajg+j) be any plane set of N+l points on which U is an 15-tree with association a. Suppose the labelling of points in I s such that a^>a2 i n t n i s order in a have no brackets or comma separating them. We now consider the set A^ = ((a^a 2),a 3,...,a^ +^}. From the equilateral construction there exists U" , an 1>-tree on A^ which has association a except that (a^a 2) is now regarded as a single point. By the inductive hypothesis we can construct U' by a f i n i t e number of Euclidean constructions. Let (a^a 2)x, the branch of U' connecting (a^a^, be replaced by the branche where s is the point of intersection of the c i r c l e through (a^a 2), a^, a 2 with the line (a^a^x. The resulting tree U, by the equilateral construction, i s the (unique by note (iv) Page 13) S-tree on with association a. Hence the Lemma by induction. Lemma 3. The set of a l l minimum length S-trees on A = {a^,.,.,a) is f i n i t e and may be constructed by a f i n i t e number of Euclidean constructions. Proof. Any two points formed by combining the elements of A by the above equilateral point bracketing notation we c a l l an association of A. Then the set of a l l assocations of a l l S-trees on A is a subset of the f i n i t e - 15 -set of a l l associations of A (in fact a proper subset for n > 3). If for each b € <f?) we perform the f i n i t e number of Euclidean constructions (Lemma 2) that constructs the S-tree on A with association b ( i f such a tree exists) we w i l l construct a l l the S-trees on A. Hence the Lemma. For the main theorem of this chapter we s h a l l need to refer to Prim's e f f i c i e n t algorithm for (C^) : Given n compact, connected, disjoint sets W^,...,Wn>to connect them together by the shortest tree(s) whose vertices are exactly these sets. The method is as follows: (1) Join to i t s nearest neighbor, say W2, (2) Replace and W^ by their union. (3) Repeat the same procedure for the new class of (n-1) sets and keep on repeating u n t i l only one set remains. Actually, Prim's algorithm was originally intended for the case of points; however, i t works equally well for sets. Moreover i f the nearest neighbor of some can be connected to i t by several segments of the same minimal length, or i f has several nearest neighbors, we perform the connection in a l l possible ways and get then the set of a l l connecting trees of the same minimal length. Theorem 3. For every n, there exists a f i n i t e number of Euclidean constructions yielding a l l the minimising trees of the problem (S ). n The minimising trees of (S Q) are precisely the minimum length S-trees on A, each of which has minimum length components (Lemma 1) on some division of A. The following method, therefore yields a l l solutions of ( S R ) . 1. From the f i n i t e set 01 = {Oi^..., Ot^) of a l l divisions of A. 2. For each Qt^ • t ^ ^ , A i 2 ' * * * , ^ i t ' ^ i ^ ' w e c o n s t r u c t °y a f i n i t e sequence of Euclidean constructions, the f i n i t e set C^j of a l l minimum length S-trees on A^ (j » l , . . . , t ^ ) . (Lemma 3.) 3. If C^j = (j) for any j = I,..., t^, (there may not exist an 13-tree on an arbitrary set of points), we reject the division (H ±- I f each 4 w e c a l 1 Ol± "admissible". - 16 -4. For each admissible division 01 ^ w e n o w form the f i n i t e set T i = U U ^ D ^ , . . . , ^ ^ ) : U t J 6 C i j } . 5. For each element of P we connect the 0.. to each other i i j and the residual set R^ i n optimal way(s) so that the resulting tree(s) on A have minimum length. (S-trees on non-disjoint sets A. ,A. are automatically joined). ip lq Prim's algorithm may be used to effect the joining. We note that the application of this algorithm must not contradict any of the properties P1-P5 on the resulting tree could not have minimum length e.g. every connection must be a segment joining two a-points. The number of optimal joinings is certainly f i n i t e . We thus obtain a f i n i t e set of trees on A from which we select the set with minimum length. (V = $ i f Ot is not admissible). Then the solutions of (S ) are 1 1 JJ n precisely the minimum length trees of the set j^-^i w^^ c n n a S been constructed by a f i n i t e sequence of Euclidean constructions. This completes the proof of the theorem. We conclude this chapter with a diagram of an S-tree on A = (a^,...,a^) which has two component S-trees V^V^ o n s e t s kl - (a 1,a 2,a 3,a 4) and A 2 = {a 2,a 5,a 6,a 7,a g,a g) respectively. The residual set R is f a ^ o , a l l ^ a n c l t* i e c o r r e s P o r i c l i n 8 division of A is 01 - (A 1,A 2,R). - 17 -Fig. 4 . - 1 8 -IV - (S^) for sets in E". We now discuss the extension of the techniques of Chapter III to the problem (S n) for n compact, connected, disjoint sets A^,...,An in the plane. Let U be a minimising tree of (S^) which has additional vertices s^,...,s . An end point of a branch of U i s either a point in B(A^) or a vertex s^. The following properties of U are simply deducible by the same methods as their counterparts in Chapter I I I . Ql. Two branches may not intersect except at an end point. Q2. I f two branches share an end point, they subtend there an an angle > 120°. Q3. For each s± ( i = l , . . . , k ) , w(si> = 3. Q4. Each s,^ is the Steiner point of {s^}, where {s^) is the set of three end points of branches joining s^. Q5. 0 < k < n-2. 2 Definition. Let A,B be compact, connected sets in E and let (ab) be defined as in Chapter III.We define the equilateral sum (AB) of A and B by (AB) = {(ab) : a e A , b € Bj. (AB) i s compact and connected. (AB) 4 (BA). If A is a point, (AB) and B are congruent under a rotation of 60° about A. I f c is a boundary point of (AB) then c = (ab) where a,b are boundary points of A,B respectively. Distributive laws hold. If A = C U D then (AB) = (CB) U (DB) and similarly for B = E U F. The following properties hold for (AB) whenever A and B have them: convexity, arcwise-connectedness, being the smooth boundary of a region, being a simple polygon. Let d(X,Y) denote the distance between two compact, disjoint sets X,Y. Lemma. (Generalised equilateral construction). 2 Let k^,k^,k^ be three compact, connected, disjoint sets in E . Suppose that a minimum length tree U connecting these sets consists of three - 19 -straight segments a^v, a^v, a^v , (a^ € B(A^)), meeting at an additional vertex v and let the rotation a^ -» a^-*a^-^-a^ be counter-clockwise about v. Then ( i ) a ^ a ^ ) , a ^ a ^ ) , a ^ a ^ ) intersect in v, ( i i ) a 1 ( a 2 a 3 ) = d(A]_, ( A ^ ) ) = a 2 ( a 3 a l ) = d ( A 2 ' ( A 3 A 1 ) } - a 3 ( a i a 2 ) = d ( A y (A LA 2)) = L(U). i.e. a^,a2>a3 are selected in A^,A2,A3 so that a^(a 2a 3) is a shortest segment connecting A^ and (A 2A 3) etc. Proof. v i s the Steiner point of a^,a 2,a 3 and therefore by the equilateral triangle solution of (S^) in Chapter I I I , a ^ a ^ ) , a ^ a ^ ) , a^a.^) intersect at v and the length of each of these segments is equal to L(U). Hence D is a minimising tree i f and only i f a^(a 2a 3) ( or similarly a 2(a 3a^), a 3(a^a 2)) attains i t s minimum value i.e. a^(a 2a 3) = d(A^,(A 2A 3)) as required. The problem (S^) for a class A of n sets [A^,.,.,A^} can now be solved from the properties Q1-Q5 and the generalised equilateral construction by exactly the same sequence of steps which solved (S Q) for points using P1-P5 and the equilateral construction. We form the f i n i t e set of a l l divisions of the class A. A division of A has the form (o^O^,...,Ctg r) where each and r i s a subclass of A. We find the minimum length S-trees on each of each division and join together these components optimally using Prim's method. The components are constructed using the association and axis technique as before. The higher equilateral sums e.g. ((A,,A^) (A^A^)), are unambiguously defined, and by an axis e.g. [ ((A,^) (A^A^)), (A^A3)] we understand the straight segment joining points in X = ((A,^) (A^A^)) and in Y = (A^Aj) for which the minimum d(X,Y) is attained. We note the following: Theorem 4. Let A = (A^,...,A^j be a class of n simple polygons. Then minimum length trees on A can be found using a f i n i t e sequence of Euclidean constructions. - 20 -To prove this i t suffices to observe that: (a) the equilateral sum of two polygons i s a polygon and hence constructible by Euclidean means. (b) the closest distance between two polygons can be found by Euclidean means. Fig. 5 . shows that there may be an i n f i n i t e number of minimum length trees connecting a family of polygons. A = [A^,A.^,A^} where A^^A^ are equilateral triangles and A^ is a single point. I t is easily v e r i f i e d , using the generalised equilateral construction, that i f a^> a2 a r e a n y P a l r of points of X^Y^, %2^2 w n* c' 1 a r e s y m m e t r i c a l l y placed with respect to A^ then the network U has minimum length. Fig. 5 Theorem 4 leads immediately to Theorem 5. Let A = {A,,...,A } be n sets and suppose that each A. is I n I a r b i t r a r i l y well approximable by simple polygons. Then minimum length trees on A can be found by a f i n i t e sequence of Euclidean constructions to within arbitrary accuracy. For i f A^ and are approximated by the polygons P^ and P^, then (A,A^) is approximated by (PjP^). - 21 -V - (S ) IN OTHER METRIC SPACES X nif 1. Euclidean m-Space. Theorem 6. The minimising trees of (S n) for n points in E m (m > 3) have the properties P1-P5 lis t e d in Chapter I I I . Proof. We show that each vertex of a minimising tree U which has a-points a^,...,aQ and s-points s^,...has valency < 3. For suppose U has a vertex x and branches xx^ along the directions of the unit vectors u^, (i=l,...,4). Then one of the angles at x (say K^TCK^) is less than 120° since u ' U j < - — for a l l i 4 J implies that 2 r 4 ~]2 4 2 w = Z u = L u + 2 Z u - u, [ i = l i j i=l 1 i | j 1 J < 4 + 2 .6.(- \) « -2, which is impossible. I t follows that xx^,xx^ is not the minimum length network connecting xx x contrary to assumption. The rest of the proof is 2 identical to that given for the properties P1-P5 in E . 3 2. A Surface in E . 3 Let D be a surface in E free from singularities of any kind. I t w i l l be shown that minimising trees of (S n) in D have properties identical to those for E m. We f i r s t prove two results which show that the 120° property of additional vertices holds in D. Suppose A, B, C are distinct points in D and P 4 {A,B,CJ minimises the sum p (P,A) + p (P,B) + p(P,C), we prove that the angles at P between the geodesies PA, PB, PC are each 120°. Let ^?(P,A) = a, p(P,B) = b and p (P,C) = c. Consider the geodesic ellipse E (= the locus of points Z such that iO (Z,A) + p(Z,B) = a + b) and the geodesic c i r c l e >0 (Z,C) = c. These closed curves touch at P, for otherwise there would be a point Y interior to both curves such that (Y,A) + p (Y,B) < a + b and p (Y,C) < c contradicting the minimum property of P. Since geodesic PC meets (Z,C) = c orthogonally, geodesic PC meets E orthogonally. By a result of classical Differential Geometry [8] page 120, E bisects the angle between the geodesic parallels p (Z,A) • a and ^o(Z,B) = b and therefore, since the geodesies AP, BP meet these circles orthogonally^the angles a and B of Fig. 6. are equal. - 22 -Fig. 6. . •. (5) 4 - A p c = 4-B P C-Similarly by considering the geodesic ellipse p ( Z,A) + p (Z,C) = a + c we prove ^.APB = .^BPC and this together with (5) proves the result. Secondly we show that i f ABC is a geodesic triangle on D with the angle at A less than 1 2 0 ° , then A does not minimise the sum p (Z,A) + ^>(Z,B) + p ( Z,C). Let V be an e-neighborhood of A s u f f i c i e n t l y small so that for a l l r, s € V there is only one geodesic joining them. Let B(V) intersect the geodesies AB, AC in X and Y. Consider the following 1-1 mapping of the geodesic triangle AXY onto the tangent plane at A. For Q in the geodesic triangle AXY with p(A,Q) = q, the corresponding point Q' is the point on the tangent line to the geodesic AQ at A such that AQ1 = q. Since the angle A of the plane triangle AX'Y' is less than 1 2 0 ° , there exists P1 in the tangent plane such that AP' + X'P' + Y'P'< AX' + AY' and furthermore the difference is proportional to € i.e. AX' + AY' - (AP' + X'P' + Y'P') = ek^ for some k^ . - 23 -If € i s s u f f i c i e n t l y small, for a l l Q^Q^ € V, |Q| Q2 - p(Q1,Q2)|< L where L i s constant. Hence i f P € V corresponds to P' i n the tangent plane, |(AP' + X'P' + Y'P') - I p(A,P) + p(X,P) + f>(Y,P)}| < k 2€ 2 for some k 2 < { p(A,X) + p(A,Y)} - ( p(A,P) + p(X,P) + p(Y,P)j (AX' + AY') - (AP' + X*P* + Y'P') + (AP' + X'P* + Y'P') - ( p(A,P) + p (X,P) + p(Y,P)) 2 > k^ £ - k 2€ > 0 i f € is su f f i c i e n t l y small. .'. p(A,X) + p(A,Y) > p(A,P) + p(X,P) + p(Y,P). If we now add >^(X,B) + p (X,C) to each side and apply the triangle inequality on the right we obtain p(A,B) + p(A,C) > j»(A,P) + f(B,P) + f(C,P) showing that A does not minimise p(Z,A) + >^(Z,B) + ^3(Z,C) as required. Using these 120° properties and proofs identical to those for P1-P5 (Chapter I I I ) , we deduce that U, a minimising tree of S q in D with extra vertices s^,...,s^, has the properties P1,P2,P3,P4 and the following analog of P5: P'5: For each i = l,...k i f (s^) contains points P^t<l^f r^ then each of the angles at s^ between the geodesies P ^ j / ^ l j 8 j / 1 ^ ^ *-s 120°. 3 . Plane Minkowski Metric Space. Let E be a centrally symmetric convex surface in E m with centre 0. The m-dimensional Minkowski metric space M11 associated with Z is obtained by defining the distance p (x,y) for x,y e E m as follows. If x = y, p (x,y) = 0. If x 4 y let the ray with i n i t i a l point 0 which is parallel to xy meet Z at P. Then p (x,y) = xy/OP, where xy and OP are usual Euclidean distances. M™ is a metric space satisfying the three conditions of the introduction and having the following properties ([9] page 21),x and y are considered as m-dimensional vectors. For a l l x,y £ M* - 24 -( i ) p (x,y) = p (0,x-y) and more generally, any translation is an isometry. ( i i ) The triangle inequality is s t r i c t provided that £ is s t r i c t l y convex and the three points involved are non-collinear, ( i i i ) For L s t r i c t l y convex p (0, x+y) < p(0,x) + p>(0,y) and this inequality is s t r i c t unless 0,x,y are collinear with x,y lying on the same side of 0. Small results in the necessary preliminary theory of this section w i l l be termed propositions and the principal results are Theorems 7 and 8. 2 For the rest of the section M w i l l mean a plane Minkowski metric space, the defining curve of which i s s t r i c t l y convex. 2 Proposition 1. Given n distinct non-collinear points a^,...,& i n M . There exists a unique point z minimising the function n f ( Z > = i=l |°(z'ai>* Proof. The existence of a minimum point was proved in Chapter I I . Suppose, contrary to the proposition, that f(z) has minima X. at and z^. Then • I f - V o ) i n i n (6) < - ^ >^ ( z 1 - a 1 , 0) + 2 ^ |°(Z2"ai'°> ( T R I A N 8 L E L A W z^,z 2 and some a^ are non-collinear since we are given that not a l l the a^ are collinear. Hence the inequality (6) is s t r i c t proving that - 25 -(7) f * Z l )< | f ( Z l ) + | f ( z 2 ) = \/2 + X/2 = X. (7) contradicts the assumption that X is the minimum and also shows that f(z) is strictly convex. The next few results concern the unique point P which minimises 2 p (P,A) + ^(P,B) + |0(P,C) where A,B,C are distinct points of M . We shall use the following abbreviations: P = min p {ABC} for the above point, Q{ABC) for the sum ^ (Q,A) + |°(Q,B) + f (Q>C) and AB for p (A,B). We omit the proof of the following Proposition 2. Let P = min p> {ABC} then P lies within or on the triangle ABC. Proposition 3. Let P = min p{ABCj and suppose I | [A,B,C). Then if A' is any point of the line PA between P and A, P = min p {A'BC). Proof. Suppose the contrary and min p{A'BC) = Q 4 P. Then A'Q + BQ + CQ < A'P + BP + CP. .*. (AA' + A'Q) + BQ + CQ < A'P + BP + CP + AA' = AP + BP + CP. Applying the triangle inequality on the left we obtain Q{ABC} < P{ABC}, contradicting the hypothesis P = min | 0 {ABC}. Proposition 4. Let P = min / O (APBJ. Then for a l l A',B' on PA, PB on the same side of P as A,B respectively P = min ^o(A'PB'). Proof. Case (i) Let A',B' be between A and P, B and P respectively and suppose the contrary. Then there exists Q such that A'Q + B'Q + PQ < A'P + B'P. .'. (A'Q + AA') + (B'Q + BB') + PQ < (A'P + AA') + (B'P - f BB'). Application of the triangle inequality to the terms bracketed on the left gives Q{ABP} < P{ABP] contradicting the minimum property of P. - 26 -Case ( i i ) I f conditions of Case ( i ) are not satisfiedjdraw A"B" par a l l e l to A'B' with A",B" satisfying these conditions (see Fig. 7). Then by Case ( i ) P = min p {A"PB"} and by similar triangles P = min o{A'B'P) as required. Fig. 7. Proposition 5. Let min p (ABC) = B and A1 be any point on the line AC but not i n the closed segment AC. Then B = min jO (A'BC). Proof Take points R,S,T on BA', BA, BC respectively such that BR = BS = BT. By hypothesis and Proposition 4 j min p {EST} « B. Suppose the contrary of the Proposition i.e. min p {A'BC} 4 B. This implies by Proposition 4 that (a) (b) Fig. 8. - 27 -(8) min p {BRT} = P 4 B. There are two cases to consider: Case ( i ) P l i e s on or to the l e f t of BS (see f i g . 8a) . Let PT meet BS at X, (internally since the unit b a l l Z of the metric i s s t r i c t l y convex). Then BX + SX + TX « BS + TX = BR + TX < BR + TP < BP + RP + TP by the triangle inequality. < BR + BT by Equation ( 8 ) . = BS + BT . i.e. X IBST} < B(BST). Contradiction since B = min pO(BST). Case ( i i ) P l i e s to the right of BS ( f i g . 8 b ) . Let PR meet BS at X. How P = min p (BRT) implies by Proposition 3 that P = min p{BXT). Using the uniqueness property^B 4 m i n f ( B X T ) and therefore by Proposition 4 . B 4 m i n (° (BST). Contradiction. Cases ( i ) and ( i i ) together prove the proposition. Definition. Let PA^PA^ PB^, PB 2 be four lines from P meeting a line ST not through P i n A^,A2,B^,B2 respectively such that B^ and B 2 are contained in the closed segment A^A2> We say that ^_A^PA2 contains 2J. BjPB 2 and properly i f B^ or B 2 or both is in the open segment A^A2» Proposition 6. ( i ) I f P = min p {BjPB^ and 2$. A^PAj contains H^B^PB^ then P = min p (A^PA^ ( i i ) I f B = min p (ABC) and P is any point within or on triangle ABC except on AC, then P = min ^(APCj. Proof ( i ) is immediate from the above definition and Proposition 5 . Tc prove ( i i ) draw parallels to AB, BC through P and let these meet AC in X and Y. Since 4 XPY is a translation of 2^ . ABC, P = min p {PXY). Then by part ( i ) , P = min p{APC} as asserted. - 28 -Proposition 7. I f C = min p {ABC} there exists A' between A and B on the line AB such that for a l l X on this line between A' and B, min p {XBC} 4 c -Proof Let the metric b a l l centre B through C cut AB at A'. A' is between A and B since AB is the "longest" (in the sense of the metric) side. Then for a l l X between A* and B, XB < A'B. .'. XC + XB < XC + A'B = XC + BC. (by construction A'B = BC). i . p . ^fXBC) < C[XBC} hence C ^ min p {XBC}. Definition ^_ ABC is a c r i t i c a l angle i f and only i f ( i ) min p {ABC) = B and ( i i ) min p{A'BC'} 4 B for any A', C such that Zy. A'BC is properly contained in 2y.ABC. Propositions 4 and 7 show that this definition is meaningful and c r i t i c a l angles exist. For the Euclidean metric, c r i t i c a l angles are 120° angles. In Minkowski spaces c r i t i c a l angles w i l l vary i n their Euclidean magnitude. Proposition 8. ( i ) C = min p (ABC) i f and only i f 2y.ACB contains a c r i t i c a l angle. ( i i ) In any triangle exactly one angle or no angle contains a c r i t i c a l angle. ( i i i ) The angle v e r t i c a l l y opposite a c r i t i c a l angle is i t s e l f c r i t i c a l . Proof ( i ) follows from the d e f i n i t i o n ^ ( i i ) is immediate from the definition and the uniqueness of the minimum point, ( i i i ) i s proved using similar triangles. We now prove our principal result on the minimising point of a triangle: Theorem 7. For any triangle ABC In V? exactly one of the following occurs: Either ( i ) Exactly one angle (say BAC) contains a c r i t i c a l angle and A » min p[ABC) or ( i i ) There exists a unique point P at which the sides of the triangle subtend c r i t i c a l angles and P « min p (ABC). - 29 -Proof ( i ) Suppose 2^ -BAC contains a c r i t i c a l angle. Then no other angle of ABC contains a c r i t i c a l angle and A = min p {ABC}. (Proposition 8) ( i i ) Suppose no angle of ABC contains a c r i t i c a l angle, then P = min p {ABC} i s not at a vertex. Now assume that ^.APB does not contain a c r i t i c a l angle. Then (9) min p {APB} = X 4 P. CX < PX + PC. (triangle inequality) .'. AX + BX + CX < AX + BX + PX + PC < AP + BP + PC . by (9). i.e. X (ABC) < P{ABC} contradicting the minimum property of P. Therefore 2^. APB (and similarly 2^APC, 2^BPC^contains a c r i t i c a l angle. We continue the proof by showing that there exists only one point at which each angle subtended by a side of the triangle contains a c r i t i c a l angle. Suppose the contrary, then there exist two such points namely Q and F = min p {ABC}. We consider two separate cases: Case 1. Assume P i s s t r i c t l y inside triangle BQC and AP meets QC in X. Then since Q = min p{QBC), Proposition 6 implies that X = min ^ o{XBC). But P = min p(ABCJ. Therefore, by Proposition 3, P = min p (XBC) which contradicts the uniqueness of min p{XBC). Proofs for P s t r i c t l y inside AQC or AQB are similar. Case 2 . Assume P l i e s in the open segments QA. 4>AQB contains a c r i t i c a l angle, therefore 2^ .APB properly contains a c r i t i c a l angle and there exists a point R on the open segment CP such that 2^ .ARB contains a c r i t i c a l angle. 2^ .s ARC, BRC also contain c r i t i c a l angles (Proposition 6), hence each angle subtended at R by a side of A ABC contains a c r i t i c a l angle. We now apply Case 1 using R instead of Q and obtain a similar contradiction. To complete the proof of Theorem 7 we have only to show that i f the angles subtended at a point P by the sides of triangle ABC, contain c r i t i c a l angles then these angles are exactly c r i t i c a l angles. Suppose the contrary and 2^ -APB properly contains a c r i t i c a l angle. Then by - 30 -Propositions 5 and 7 there is a point D on AB such that for a l l A' in the closed segment AD, the angles subtended at P by A'B, BC, A'C each contain a c r i t i c a l angle and hence for a l l such A', P = min p {A'BC} which is impossible with a s t r i c t l y convex unit b a l l . Hence the Theorem. Proposition 9. I f of the three angles subtended by AB, AC, CA at P, two are c r i t i c a l , then the third is c r i t i c a l . Proof. Suppose 2^. APC, Zy. BPC are c r i t i c a l and t\. APB does not contain a c r i t i c a l angle. Then min p {APB} = X \ P and by Theorem 7 the angles PXB, PXA, AXB are c r i t i c a l . Draw parallels to AX, BX through P and produce XP. We see that one of the c r i t i c a l angles APC, BPC (in Fig. 9 i t is 25y APC) properly contains a c r i t i c a l angle which is impossible. Therefore 2^ _APB contains a c r i t i c a l angle and by Theorem 7 i t is a c r i t i c a l angle. Fig 9. - 31 -Corollary 1. If of 3 angles at a point, 2 contain c r i t i c a l angles, one of thera properly, then the third angle does not contain a c r i t i c a l angle. Corollary 2. Supplementary angles cannot both contain c r i t i c a l angles. Proof Suppose the contrary and let 4»A0B, 2^ -BOC be supplementary angles each containing a c r i t i c a l angle (Fig. 10). Take any point A' within 2^. AOB' as shown. Then 2^ .A'0B properly contains the c r i t i c a l angle AOB and 2^ .B0C contains a c r i t i c a l angle by hypothesis. Hence by Corollary 1^ 2fy. A'OC does not contain a c r i t i c a l angle. But the c r i t i c a l angle B'OC (Proposition 8 i i i ) is contained in 2^A'OC. Contradiction. Fig. 10. We digress and state the following fact which w i l l be used in the next section. Suppose A,B,C are distinct points in an m-dimensional Minkowski Metric Space with s t r i c t l y convex defining surface S and l e t the plane ff defined by A,B,C meet S in the curve Z . Then the above theory holds in the plane Minkowski space defined on Tf by L i.e. we can apply Propositions 1-9 and Theorem 7 to three points A,B,C in an m-dimensional Minkowski Metric Space. - 32 -2 Theorem 8. Let U be a minimising tree of (S n) in M with additional vertices s ^ . . . ^ . Then U has the properties P1-P4 of section 3 and the following analog of P5: P"5. For each i = l,...,k, s^ = min p(xyz) where x,y,z are the points of (s^) and each angle xs^y, ys^z, zs^x is a c r i t i c a l angle. Proof Suppose branches x^y^> X2^2 *- n t e r s e c t e < 3 a t P (n°t a vertex of U) then some angle at P say X^P X2 does not contain a c r i t i c a l angle. (Proposition 9, Corollary 2). Therefore min p (x^px^} = z 4 P a n d a replacement of x^p,x2p by the three lines x^z, x 2z, pz shortens the assumed minimising tree which proves PI. Similarly, no vertex x of U has w(x) > 3. Thus U satisfies P3 and w(si> < 3 for a l l i = l,...,k. There is no gain in introducing additional vertices with valency < 3. Hence P2. 2 The proof of P4 is identical to that given for (S ) in E and P"5 is the n result of theorem 7. It is shown in [4] that for (S n) in the Manhattan metric, where the defining curve is not s t r i c t l y convex, the property w(x) < 3 for each vertex x of a minimising tree does not hold. The equilateral construction of the Steiner point of a triangle 2 in E enabled us to solve the problem (S ). Accordingly one is lead to ^ 2 search for a generalisation of this construction for P = min p (ABCj in M when no angle of A ABC contains a c r i t i c a l angle. The following two conjectures were made: (i) Let (AB) be the third vertex of the triangle b u i l t outward on AB whose exterior angles are c r i t i c a l angles. Then the line (AB)C passes through P. ( i i ) A triangle XYZ in M2 i s f> - equilaterial i f p ( X , Y ) = p ( Y , Z ) = p ( Z , X ) . Let (AB) be the third vertex of the p - equilateral triangle b u i l t outward on AB. Then (AB)C passes through P. 2 We note that in E ( i ) and ( i i ) are equivalent and may be used to construct the Steiner point. The counter examples below show that in M^ - 33 -the conjectures are not equivalent and that neither is true in general. The examples w i l l use the metric with unit b a l l |x|p + |y|P = 1, which is s t r i c t l y convex i f p > 1 Then p((x^,y^) , ^ x 2 , y 2 ^ = (Ix^xjP + | y 2 - y i | p ) 1 / p . Let A = (0,1) , B = (1,0) , C = (-1,0). Symmetry and uniqueness i n s i s t that P = min p{ABC} li e s on the y-axis and by elementary methods, the sum p (A,P) + |3(B,P) + p(C,P) takes i t s minimum value at the point P(0,X) where = ( 2 p / p " 1 - i ) 1/P Recall that i f A is moved to any point A 1 on PA on the same side of P then P = min p { A ' B C } . Example 1. To show that a triangle whose exterior angles are c r i t i c a l , is not necessarily p - equilateral. Using the special case given above, the three angles at P in f i g . 11(a) are c r i t i c a l angles since P = min p { A B C } . A P , B P , CP have slopes oo, X, -X. The sides of triangle 0RX shown in f i g . 11(b) have identical slopes and hence the exterior angles of this triangle are c r i t i c a l angles e.g. 2^ -0RQ is a translation of the c r i t i c a l angle B P C . We show that triangle 0RX is not p - equilateral. A(<v) C0,o) x ( o , i ) (a) (b) Fig. 11 - 34 -But jo(OX) = 1. Hence triangle is p -equilateral i f and only i f 2(2-p)/(p-l) m ^ i.e. i f and only i f p = 2 and the metric is Euclidean. Example 2. To show conjecture ( i ) i s false. 8 ( - i 3 o ) c ^ ° ) Fig. 12 In Fig. 12 P = min a {ABC} ; the exterior angles DAC, EC'A of triangle o ABC are translations followed by a rotation through 90 of the angles APC, APB. Since each such transformation i s an isometry for this metric, the angles DAC, ECA are c r i t i c a l angles and hence triangle ABC has i t s exterior angles c r i t i c a l . We show that CC does not pass through P. - 35 -CC has equation 3Xy = 1 - x and passes through (0,X) i f and only i f 3X2 = 1 or X = j | i.e. CC' passes through P i f and only i f p = 2 and the metric is Euclidean. Example 3. To show conjecture ( i i ) is false. Fig. 13 In Fig. 13 A,B* have co-ordinates ( 0 , ( 2 P - l ) 1 / p ) , ( 2 , ( 2 P - l ) 1 / p ) . Then i t i s easily verified that triangle AB'C is p - equilateral with sides of length 2. We show that BB' does not in general pass through P = min C (ABC). BB' has equation y = \ ( 2 P - 1 ) 1 ^ P (x + 1) hence has y-intercept (2-1) p/3. .'. BB' passes through P i f and o n l y l f p i/p P/p-1 -1/P ( 2 P - l ) i / P / 3 - (2 -1) (2 P-1)(2 P / P- 1-1) - 3 P . We see that this is satisfied for the Euclidean case p * 2 but is certainly false for any integer p > 2. - 36 -VI - MORE PROPERTIES OF (S „ ) _ naB7 In this chapter we prove two results for ( s n apy)> concerning finiteness of solution in Minkowski Space and non-constructibility of 2 solutions in E by Euclidean constructions. The following threorem uses the notation of Theorem 2. Chapter I I Theorem 9. If M is a Minkowski Metric space M for which the defining ___________ m surface Z is s t r i c t l y convex, then there is a unique tree of minimum length in C e { ^ , . . . , 0 ^ } . Proof Suppose the contrary and f has minima, value Z, at { } and [t ,*..,t^} where t ^ 4 s± f° r s o m e 1* Consider the set t s^ + t^ s k + t k Using Properties ( i ) - ( i i i ) of Minkowski Spaces Chapter V. • 2 / 5 ( V * i j > * \ f~ ( tl' V This inequality is s t r i c t unless a , s ^ t ^ are collinear with s^, t ^ on the same side of a . i j k X i ,s.+t. \ , k X i J [ 1=1 j - l ' V 2 ' a i j / - 2 i=l j - l U 1 ^ i U J and the inequality i s s t r i c t unless for each i = l,...,k, a ^ , '"> a , s , t are collinear with s , t. occupying suitable positions on the i \ ^ i i l i l i n e . Such a situation cannot occur in a minimum length tree of C. Assuming n > 2 (otherwise the problem is t r i v i a l ) , there exists i for - 37 -which \^ > 2 and joins only one other s-point. If ^ > 2 a simple application of the triangle inequality proves that the assumed tree could not be minimum length in C and the case = 2 is disposed of using Proposition 9, Corollary 2. Thus we can conclude k X i ,s 4+t. , ! k X i i k X i ( 1 0 ) ill j - I l K - V ' a i j ) < 2 iJi f ( V a i j > + 2 i = S l j ^ W ' By a similar use of the properties of we can show Adding this to (10) and I p(a.,a.) to both sides we obtain (i,j)£R2r 1 J ) < - | f(» 1,...,« k)+J £( ti'" ,' tk )" i which S l + t l S k + t k * V 2 " 2 contradicts the minimum property of Z. Corollary In Mm, (^nap^^ a m* ^ a v e a f l n l t e number of minimising trees. Proof Immediate from Theorems 1,2 and 9. Similar proofs to those given here may be used to establish identical results when the function to be minimised i s F j^L(U), w(a i) , w(s^) , k ^ where F i s any positive function which is s t r i c t l y increasing in each of i t s four variables. It was demonstrated in Chapter 1 that (S^p^,) reduces to (P^) for suitable values of the constants a , 8 , 7 . We show now that in general (P ) 2 n in E (and hence (S . ) ) is not solvable by Euclidean constructions. We use n = 5 for our example since (P^) is solvable by Euclidean constructions (by our equilateral construction). The solution of (P^) is the intersection of the diagonals i f the configuration is convex and the vertex interior to - 38 -the convex h u l l otherwise. We take 5 points ( i = 1,.«.,5) symmetrically placed with respect to the x-axis as shown in f i g . 14. A, M A>,&0 Fig. 14. The minimum point P l i e s on the x-axis with i t s co-ordinate in [0,a] I PA. - x + 2 7l+x2 + 2 A2+(a-x)2 i=l i ' Minimising this function by elementary methods;we find that the co-ordinate x of P satisfies an eighth degree polynomial equation f(x) « 0 whose coefficients are polynomials in a and b. We show that for suitable integers a,b, f(x) i s irreducible over the rationals and f(x) - 0 has Galois group over the rationals which does not have order 2^ where k is a positive integer. Therefore x is not an element belonging to an extension f i e l d of the rationals of degree 2 and hence the segment OP is not constructible by Euclidean constructions (See [10] page 185). i.e. for suitable choices of the five points (P^) i s not solvable by Euclidean constructions. - 39 -The leading coefficient of f(x) is 15. In order to use the theory of [10] page 190-191, we need to work with a monic polynomial and therefore make the transformation x = y/15 and multiply the equation through by 15 thus obtaining equation g(y) = 0 where g(y) is monic. We note that such a transformation does not affect reducibility over the rationals or the Galois group of the equation. The coefficients of g(y) are: 8 1 -60a 15 (90a 2 + 22b2 + 22) -15 2 (88a + 60a 3 + 44ab2) 15 3 (42 + 15a 4 + 154a2) -15 4 (88a 3 + 120ab2 - 36a) y y i 155 (22a 4 + 60a 2b 2 + 6b 4 + 6b 2 - 54a2) 15" -15 (b 12a 2 . (3a' 3 a 2 ) 2 b 2) We take a = 10^b = 3 and notice that the coefficients of y° and the constant are odd while the rest of the coefficients are even, so that Eisenstein's i r r e d u c i b i l i t y criterion using the prime 2 shows that g(y) i s irreducible over the rationals and hence g(y) = 0 has no multiple root. Let 1/(7) be the f i e l d of residue classes of integers modulo 7. Over this f i e l d g(y) = 0 reduces to the equation gy(y) m y 8 + 2y^ + y^ + y^ + 4y 4 + y 3 + 4y 2 + 4y + 5 = 0 . The greatest common divisor of gj(y) and i t s derivative over 1/(7) in 1, hence g^(y) » 0 has no multiple root. gy(y) has the following factorisation mod 7: (11) (y 3 + 5y + 4y + 2)(y + 4y + 5y + 4y + 6) and the cubic factor i s irreducible mod 7. Therefore the Galois group of the equation g(y) = 0 contains a permutation a whose representation as a product of disjoint cycles contains a cycle of order 3. a does not have order 2 k for any positive integer k, hence the Galois group does not have - 40 -order 2 and the proof Is complete. We state the result formally: 2 Theorem 10. (P ) and (S ) in E are not, in general, solvable by n nczp/ Euclidean constructions. Fi n a l l y , we show how the above example was found. 7 is the smallest prime which can be used. (It i s clear from the coefficients that g(y) has multiple roots modulo 2, 3 and 5). One therefore searches for values of a and b such that g^(y) = 0 has no multiple root and an irreducible cubic, quintic or sextic factor mod 7. The arithmetic being mod 7, i t suffices to consider a,b = 0, ...,6. In fact since b only 2 occurs in the coefficients as b , we need only take b » 0,1,2,3 as 2 2 b = (7-b) mod 7. The 28 polynomials were tested for an irreducible cubic factor using a d i g i t a l computer. The method used was to divide each polynomial by the f i n i t e number of irreducible cubics over.1/(7) and investigate the remainder. The values a = 3, b = 3 yielded the factorisation (11). However Eistenstein's criterion works conveniently for g(y) with prime 2 i f a is even and b i s odd so we take a = 10, b • 3. The polynomial obtained has the same reduction (11) mod 7. This method of reduction mod p in conjunction with a computing machine can provide much information on the structure of Galois groups of equations. - 41 -BIBLIOGRAPHY 1. R. Courant and H. Robbins: What is Mathematics? (New York 1941). 2. Z. A. Melzak: On the Problem of Steiner. Canadian Math. Bulletin, Vol. 4 No. 2. May 1961. 3. R. C. Prim: Shortest Connecting Networks. Bell System Tech. Journal 31, pp 1398 - 1401. 4. M. Hanan: On the Steiner Problem with Rectilinear distance. S.I.A.M. Journal of Applied Mathematics, Vol. 14 No. 2. March 1966. 5. F. P. Palermo: A Network Minimisation Problem. I.B.M. J. of Research and Development 5 (1961) pp 335 - 337. 6. R. L. Francis: A note on Optimum Location of New Machines in Existing Plant Layout. J. Indus. Eng. 14 (1963) pp 57 - 59. 7. Hua-lo-keng et a l : Application of Math. Methods to Wheat Harvesting. Chinese Math. 2 (1962) pp 77 - 91. 8. C. E. Wetherburn: Diff. Geometry of 3 Dimensions. (Cambridge 1947) 9. L. M. Blumenthal: Theory and Applications of Distance Geometry. (Oxford 1953) 10. B. L. Van der Waerden: Modern Algebra Vol. 1. (New York 1949)
- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- On the steiner problem
Open Collections
UBC Theses and Dissertations
Featured Collection
UBC Theses and Dissertations
On the steiner problem Cockayne, Ernest 1967
pdf
Page Metadata
Item Metadata
Title | On the steiner problem |
Creator |
Cockayne, Ernest |
Publisher | University of British Columbia |
Date Issued | 1967 |
Description | The classical Steiner Problem may be stated: Given n points [formula omitted] in the Euclidean plane, to construct the shortest tree(s) (i.e. undirected, connected, circuit free graph(s)) whose vertices include [formula omitted]. The problem is generalised by considering sets in a metric space rather than points in E² and also by minimising a more general graph function than length, thus yielding a large class of network minimisation problems which have a wide variety of practical applications, The thesis is concerned with the following aspects of these problems. 1. Existence and uniqueness or multiplicity of solutions. 2. The structure of solutions and demonstration that minimising trees of various problems share common properties. 3. Solvability of problems by Euclidean constructions or by other geometrical methods. |
Subject |
distance geometry topology |
Genre |
Thesis/Dissertation |
Type |
Text |
Language | eng |
Date Available | 2012-03-07 |
Provider | Vancouver : University of British Columbia Library |
Rights | For non-commercial purposes only, such as research, private study and education. Additional conditions apply, see Terms of Use https://open.library.ubc.ca/terms_of_use. |
DOI | 10.14288/1.0080622 |
URI | http://hdl.handle.net/2429/41202 |
Degree |
Doctor of Philosophy - PhD |
Program |
Mathematics |
Affiliation |
Science, Faculty of Mathematics, Department of |
Degree Grantor | University of British Columbia |
Campus |
UBCV |
Scholarly Level | Graduate |
AggregatedSourceRepository | DSpace |
Download
- Media
- 831-UBC_1967 A1 C52.pdf [ 1.79MB ]
- Metadata
- JSON: 831-1.0080622.json
- JSON-LD: 831-1.0080622-ld.json
- RDF/XML (Pretty): 831-1.0080622-rdf.xml
- RDF/JSON: 831-1.0080622-rdf.json
- Turtle: 831-1.0080622-turtle.txt
- N-Triples: 831-1.0080622-rdf-ntriples.txt
- Original Record: 831-1.0080622-source.json
- Full Text
- 831-1.0080622-fulltext.txt
- Citation
- 831-1.0080622.ris
Full Text
Cite
Citation Scheme:
Usage Statistics
Share
Embed
Customize your widget with the following options, then copy and paste the code below into the HTML
of your page to embed this item in your website.
<div id="ubcOpenCollectionsWidgetDisplay">
<script id="ubcOpenCollectionsWidget"
src="{[{embed.src}]}"
data-item="{[{embed.item}]}"
data-collection="{[{embed.collection}]}"
data-metadata="{[{embed.showMetadata}]}"
data-width="{[{embed.width}]}"
async >
</script>
</div>
Our image viewer uses the IIIF 2.0 standard.
To load this item in other compatible viewers, use this url:
http://iiif.library.ubc.ca/presentation/dsp.831.1-0080622/manifest