9332

OPTIMAL NETWORKS JOINING n POINTS IN THE PLANE

V . A * Horn

Technical Report

to

Northeast Corridor Transportation Project

NATIONAL BUREAU OF STANDARDS

NATIONAL BUREAU OF STANDARDS REPORT

MBS PROJECT

2058^56 May, 1968

MBS REPORT

9832

OPTIMAL NETWORKS JOINING n POINTS IN THE PLANE

W.A. Horn

Applied Mathematics Division

Technical Report

to

Northeast Corridor Transportation Project

IMPORTANT NOTICE NATIONAL BUREAU OF ST

for use within the Government, and review. For this reason, thi whole or in part, is not author Bureau of Standards, Washingto

the Report has beeri specifically

Approved for public release by the

Director of the National Institute of

Standards and Technology (NIST) on October 9, 2015

ss accounting documents intended

subjected to additional evaluation

listing of this Report, either in

j Office of the Director, National

jy the Government agency for winch

opies tor its own use.

U.S. DEPARTMENT OF COMMERCE

NATIONAL BUREAU OF STANDARDS

p. 20 : Last two sentences of the proof of theorem 12 should he replaced

by ( new paragraph)

Now by theorem 11, if N is any network with more than

-^n(n-l) 2 (n-2) auxiliary nodes , we may find a subnetwork of N

» connecting all initial nodes, containing a minimal path between

each pair of initial nodes, and having < -Jn(n-l)^(n-2) auxiliary

nodes of order > 3. Clearly this subnetwork dees not contain all

arcs of the original network and so, since X > 0 , y is smaller

for the subnetwork. Thus we need consider only a finite number

of values for n , namely the integers from 0 to ^n(n-l)-(n-2)

Hence there exists an optimal network.

p. 21 : Delete last two lines of statement of lemma 13, and replace by:

with costs of travel the same as in the original, except that

the cost between x and any other initial node p . is X. . . J ij

p.22, l . 4 : . Change "demands" to "travel costs" .

p.25, l.l : Comma after "nodes" .

p.2b, L. 6 : Change A" to A

1 .

p.27> fig. 5s Letter "D" is missing from figure. Insert at same location

as in figure k

p. 32: Delete first two sentences in proof of lemma 19. Replace by:

From corollary 8 we have that the vectors directed outward

from the Y in the direction of its incident arcs and having

lengths equal to the weights carried by the respective arcs

sum to the zero vector. Furthermore if the vector addition

is represented graphically, a triangle will be formed such

that the angle between any two adjacent sides is the supplement

of the angle made by the arcs of the Y corresponding to those

two sides.

2

p- 36 :

p- 38 >

p. 42,

Add the following sentence to the end of the paragraph

« preceding corollary 21:

Its statement here uses the normalization \ + X) X. . =1 , ij

mentioned previously.

1 p p

1 . 2 : \ 1-X) should be i(l-X) .

A. 13: Delete "according to the author." End sentence with a period.

*

- 3 -

ABSTRACT

This report develops a number of results on the problem

of connecting n points in the plane , with given travel

demands between each pair, by a minimum-cost networK. The

critical assunqptions are (a) constant construction costs per

mile, (b) constant travel cost per mile per traveller, and

(c) use of shortest paths in the network for all travel.

These results are adequate to give a complete solution

when n=3* For this case, the possible optimal networK

configurations are identified, each is shown actually to arise

as the optimum for suitable combinations of problem data,

and the computations necessary to choose among them are described.

One of the results for general n is an upper bound (roughly

k

n /k) on the number of nodes, other than the original n points,

in an optimal network. Another is the determination of an

explicit threshold, for the ratio of construction cost to travel

cost, beyond which each "auxiliary node" will lie on exactly three

linxs
TABLE OF CONTENTS

1. INTRODUCTION 1

2. OTHER NOTATION 4

3. CHARACTERISTICS OF OPTIMAL NETWORKS 6

4. OPTIMAL NETWORKS FOR 3 POINTS 21

5 . FURTHER WORK 43

6. REFERENCES ...45
OPTIMAL NETWORKS JOINING n POINTS IN THE PLANE

W.A. Horn

* National Bureau of Standards

1 . INTRODUCTION

This report develops a number of results on the problem of

connecting n points in the plane, with given travel demands

between each pair, by a minimum-cost network. The critical

assumptions are (a) constant construction costs per mile,

(b) constant travel costs per mile per traveler, and (c) use

of shortest paths in the network for all travel.

Stated mathematically, the problem is to construct a network,

or graph, N , in the plane, connecting the original n points

and such that the number

y(H) = Aje(w) + < i < j < n}

is minimized,

some units),

to point j ,

where X is the cost per mile of construction

X. . is the cost per mile to travel from point

ij

P. . is a selected shortest path from i to

ij

(in

i

j ,

* Supported by Northeast Corridor Transportation Project, Department

of Transportation, USA. No official endorsement is implied.
and l ( ) is the length function, i.e., X( subgraph K) is the

total length of subgraph K , defined as the sum of the lengths

of all the arcs of K .

Obviously, the original set of points to be connected will

be nodes, or vertices, of the network, and we shall call them

initial nodes. Other nodes of the network will be called

auxiliary nodes. In order to simplify the problem, we assume

that every auxiliary node is of order > 3 > that is, that it

has at least 3 arcs incident upon it, since otherwise it is

clear that it could be eliminated from the network without loss,

(if an auxiliary node were of order 2, it could be eliminated

and its two arcs combined into 1, while if it were of order 1,

it and its incident arc could both be eliminated.)

A networx which has auxiliary nodes of order > 3 and connects

the set of initial nodes will be called feasible . A network

which is feasible and minimizes y(N), above, will be called

optimal . We shall call y the value function throughout this

paper and, for convenience, shall assume that

A + L A = 1 .

(This corresponds to adjusting the unit of money.) We ©Iso require

that A > 0 , whereas A. . > C . iJ -

2
Initial nodes vill often be designated , and a selected

shortest path between p^ and

p^ may be denoted

for convenience, we define a number

Also,

w

K

= A + S

^iJ !A

K

CPU

3

as the weight carried by an arc A. of the network. This

corresponds to the cost of constructing and using the portion

of the network A

K

The problem considered is that of finding, or at least

finding properties of, optimal networKS joining any set of n

points. Mathematically, this problem has its origins in the

so-called "Weber Problem" ([ 3 ]); in which a point in the plane

is to be found such that the sum of its distances to 3 fixed

points in the plane is minimal. This has been generalized to

the case of finding a point the sum of whose distances to n given points is minimal (see [2], for example), and to the socalled "Street NetworK." problem ([l]). The latter problem

involves finding in the plane a tree of shortest length connecting

a given set of n points; it has not been solved generally.

This paper presents a discussion of some characteristics of

networks which are optimal for the. problem under consideration,

and a complete listing of all possible optimal networks for the

case n = 3 > together with a method for finding the optimal solutions

on 3 points. In the course of the discussion, a bound is derived

for the number of auxiliary nodes in a networK on n points, a result which can easily be extended to more general, non-planar networxs

- 3 -
2. OTHER NOTATION

Other conventions which will be used in this paper are the

following. For any points A and B in the plane, AB will

represent the line segment from A to B , AB the line containing

—

A and B , and AB the ray with initial point A and passing

through B . We also shall use [A,B) and (A,B] to denote

the line segment from A to B except for point B or A , respectively (the half open segment). An angle ABC , with vertex

B , will often be written as ABC rather than < ABC . Distance

between points A and B will be denoted by ||A-B|| .

A similarity transformation is a transformation T of the

(x,y) -plane into itself given by

T(x,y) = S^T^y))) ,

where

end

T^: x -* ± x + a

y - ± y + b ,

R : x -* x cos 0 + y sin 0

y

-* x sin 0 - y cos 0 ,

S : x -* ocx.

y ^ ay (a > 0) .

- k -
It is well known that similarity transformations preserve angles

and multiply all lengths by a fixed quantity. The ratio of

length of T(AB) to length of AB will be called simply the

"ratio" of T . (Note that this ratio is equal to the a of

S , above.)

- 5 -
3 . CHARACTERISTICS OF OPTIMAL NETWORKS

We nov derive some results concerning optimal networks

joining n points. In the next section we will consider the

special case of n = 3 •

Lemma 1 . For any optimal network N ,

y{N) = Z v

i

i(A.) , i

where the summation is taken over all arcs A^ of N .

Proof . W

Te have

y(N) = ZK A(P ) + AX(n)

J,k J J

= = c

/(A

i

} ]

+ A £ " (A

i

}

J,k A c P 1

1 jk

= Z(z X + X)i(A.)

1 A

i

c V = £ w X(A )

. i

Lemma 2 . In an optimal network, all arcs are straight

line segments.

Proof . Consider any arc A. of N , an optimal network. Since

A > 0 by assumption, w > 0 . If A. is not a streight line,

then replacing A^ by a straight line joining its endpoints

decreases X(A^)By lemma 1, y(N) is thereby decreased, a

c ont ra di ct i on

- 6 -
Lemma 3

Any optimal network is connected.

Proof. If N is an optimal network which is not connected,

then all of the initial nodes of N must lie in some connected

component , since otherwise some pair of initial nodes

would not be pathwise connected, contradicting the definition

of an optimal feasible network. But then all other components

of N may be deleted from N and, as in lemma 2, y( N) will

be decreased.

Lemma k .- Every arc of an optimal networK is part of some

minimal path

Proof. If some arc A^ lies on no minimal path, then removing

from the networK reduces y(N) by XX(A^) .

Lemma 5 • Every optimal network is contained in the convex

hull of its initial nodes.

Proof . Let C = co([p^}), the convex hull of the set of initial

nodes {p ^ } . Define a mapping P of the plane onto C as

follows. For xeC , P(x) = x . For x^C , let ye C be a point

such that ||x-y|| is the distance from x to C . Such a point

exists, since C is compact. Furthermore, y is uniquely

determined, since if y’^y is another point of C for which

l|x-y|| = llx-y’ll , then

- 7 -
I|x-|(y+y')|| < i(||x-y|| + ||x-y'||) = ||x-y|| ,

with strict inequality holding for all cases in which x,y, and

y

f do not lie on the same straight line, (This will always

be the case if ||x-y|| = ||x-y’||.) But -§-(y+y l ) lies in C , since C is convex, and hence

d(x,C) < i|x-|(y+y’)|| < ||x-y|| ,

a contradiction.

Define P(x) = y in this case.

Since C is an r-sided convex polygon, it is clear that

P(x) lies in some side, or is some vertex, of this polygon

whenever x is exterior to C . If P(x) lies in the interior

of some side, then x-P(x) is perpendicular to this side. Thus

the set of points in the exterior of C which are mapped into

some side S, by P is just the set of all half lines emanating

x from and perpendicular to S, . Call this set E . Also, let x x

denote the set of all points mapped into vertex p^ . (See

figure 1.)

Now consider the network P(n), where N is any optimal network

for the p^ . Since P is obviously continuous, all paths

connecting nodes of N are transformed by P into paths connecting

the same nodes in P(n) . Thus P(n) is a feasible network for

- 8 -
Figure 1. Illustration for Lemma 5*

- 9 -
the set of points £p . } We nov show y(p(N)) < y(N) if N

contains points in the exterior of C .

Let L be any line segment of N in the exterior of C . Then

L = U(L n E ) U U(L fl F. ) K . 1

K 1

and so

But

£(L) = S X(L n E. ) + S A(L n F.) . k

K

i

1

p(l) = u p(l he,) u u x(l n f. )

, K. . 1

and

From this

J5(P(L)) = s A(P(L n E ) ). IV K

it is clear that

A(P(L)) < A(L)

with equality holding only if L lies in some E and is parallel

K. to S . However, if all line segments in the exterior of C

satisfied this condition, then N would not be connected,

contradicting lemma 3* Thus

y( p(n)) < y(N) ,

contradicting the optimality of N . This completes the proof.

10
Theorem b . If an optimal networK N has n initial nodes, then

each initial node is of order < n-1 and each auxiliary node is

of order < n . Furthermore, every arc incident on an initial

node must carry at least one minimal path from that node to

some other initial node in any assignment of minimal paths.

Proof. Let p be any node of an optimal networK N with some

given assignment of minimal paths. Let A^,A^,...,A^ denote

the arcs incident at p . Then by lemma ^ each A^ carries at

least one minimal path P. going from p to (say) initial

J K

node p. . Thus for each j from 1 to n , it is possible to

J define f(j) = A_^ , where A is some arc at p carrying a minimal path to p . , or f(j) = if no path from p. contains p

J J

Now if more arcs leave p than there are remaining (other

than p) initial nodes, then clearly there exists some A^ not

of the form f(j). But the portion of any minimal path containing

A^ and going to p_^ may be changed to lie along the path from p

to p^ via f(r), since it is clear that the latter path must

be minimal between p and p_^ . After all such changes of minimal

path have been made for A^ , no minimal path will contain A^ .

Thus, by lemma h, N is not optimal.

From this, it is seen that the number of arcs incident at p

is at most n if p is an auxiliary node and n-1 if p is an

initial node. The last part of the theorem follows from the

11
statement that if p = p . , an initial node, then the fact that

some A. incident at p. carries no path P implies that all

1 J JK

paths entering p. via A. may he shifted to other arcs, as

J i

above, again contradicting lemma t. This completes the proof.

Lemma J . Let p be an auxiliary node in an optimal network

with arcs (straight lines)'12m A-.A^,...,A incident at p .

Impose a coordinate system with origin at p . Let 0 be the

angle made by A_^ with the positive x axis and w^ the weight

carried by arc A^ . Then

m

£ w. cos 6. = 0 .

. , i l

Proof . Consider the diagram of figure 2, where is the length

of arc A , Ax a distance from p^ to a new point p

T along

the x-axis, the length of a new line A^ drawn from the

other vertex of A.' to p’, and 40. the angle between A. and A! . i i ii

Then, by the Law of Sines,

i\

l

sin 0

i

Ax

sin(0.+A0. ) sin A0. v l i i

or

l.

l = -OX

sin(0.+A0.

i i

sin iid.

l

V.

i = Ax sin 0

sin A0.

12
Y

Figure 2. Illustration for Lemma J.

- 13 -
, , a A sin 0. - sin 0.cos *a. - cos 0. sin A0. Thus i]

l

- X

l

. = Ax —

i ii ii—

sin A0

i

a n sm0. (l-cosA8.

= Ax -cos0. + i

v i' 1 l

V sinA6.

Letting Ax , and hence A0^ , go to 0 , we get

dJL. —^ = -cos0. . dx l

It is clear that the total directional derivative of y with

respect to moving p in the direction x will he

dx

m

2 w . ( -COS0 . )

. 1 1 i=l

Setting dj/

dx

for optimality gives the required equation.

Corollary 8 . Let v. he the vector of length w^ and angle 0^ , where w. and 0. , are as in lemma J. Then

i i

m

£ v . = 0 . i=i 1

IT Proof By rotating the coordinate axes through — in lemma "J

we have also

m

£ w. sin0. = 0 . i=l 1 1

- 14
[Note that the results of lemma 7 and. corollary 8 are not

new. A slightly different proof of them is given in [ 2 ] , where it is also shown that the placement of p which minimizes

the function

r v

i ||p-p i

|| i

is uniquely given as that point where

L v . = 0

i

l

if such a point exists. If no such point exists, the optimal

placement of p is at a vertex.]

Next we turn our attention to more general networks containing

arcs with given positive lengths assigned to them. We call such

networKS "measured”

Lemma 9 Let N he any measured networK, not necessarily

planar. Suppose that for some subset S of nodes it is true

that the minimal path connecting any two nodes of S is unique.

If any two nodes p and p’ are contained in each of two

minimal paths and connecting nodes of S , then the

part of P^ which connects p and p’ is identical with the part

of P^ which connects p and p' .

- 15 -
Proof . If there were two paths between p and p' , one a part

of and the other a part of P^ , then each would have to be

the same length,, by the minimality of P^ and P^ . But then

either could be used as the part of P^ or P^ connecting p

and p’, contradicting the uniqueness of P^ and P^ .

Theorem 10 . Let N be any measured network, not necessarily

planar. For any subset of nodes S , it is possible to choose

minimal paths connecting pairs of nodes in S so that if any

two nodes p and p

r of N lie on minimal paths P^ and P^ , then the part of P^ which connects p and p’ is identical

with the part of P

p

which connects p and p

f

.

Proof . Let 77 be the minimum (positive) difference in length

between a shortest path and a next shortest path connecting any

pair of points in S , and let m be the total number of arcs

of N . Define

= 77 • 2 , i = 1,2, ... ,m,

arid let

v

i = h

+ >

where j£_. is the length assigned to arc A^ . If we assign the

new length to arc , it is clear that no two paths joining

any pair of points In S can both be minimal and that any path

- 16 -
joining two points of S which is minimal under the new length

assignment was also minimal under the old assignment. By lemma

the assignment of minimal paths using the new lengths satisfies

the statement of the theorem.

We now use theorem 10 to obtain a gross upper hound on the

number of nodes in any optimal planar networK. This will then

allow a proof of the existence of an optimum configuration for any

set of initial nodes.

Theorem 11. If ' N is an optimal planar networK on n initial

nodes , then the number of auxiliary nodes of N is bounded by

n

a 1 in(n-l)

2

(n-2) .

Proof . Choose minimal paths in N satisfying the conditions of

theorem 10. If P and P are any two minimal paths meeting

i j kX

at some auxiliary node p of N , then it is clear that P

and P

^ must exhibit exactly one of these behaviors:

ij

(a) "Continue” at p . In this case two arcs

incident at p both carry P and P^

or

(b) "Separate" at p . In this case, one arc incident

at p carries P. . and P. . , another carries

ij kX 3 only P , and a third carries only P, . . I j Kx

- IT -
or

(c) "Cross” at p . In this case two separate arcs

incident at p carry P^ . and two other arcs

carry .

But from theorem 10 it is clear that P (1 P. . is connected,

1

kjo

and hence there is at most one point at which P. . and P. . 1 j KXj can cross and at most two points at which they can separate.

In fact, if { i , j ]

fl {k,i} ^ fi , then there is at most one point at which they can separate (they cannot cross at an

auxiliary node), since the two paths must be common at their

common initial node.

We now count auxiliary nodes on a given minimal path P.

J at which P. . and some other oath P . either cross or separate

ij kJL

If {i, jj H {k,jfcj = 0 , there are at most two such points and at

most -|(n-2) (n-3) such {k,X} sets. Thus there are at most

(n-2)(n-3) such auxiliary nodes. If {i,j} fl {k,i} ^ 0 , there

is at most one such point, with 2(n-2) possible {k,^} sets.

Thus, altogether there are at most

v (n-2)(n-3) + 2(n-2) = (n-l)(n-2)

auxiliary nodes on P at which P. . and some other path cross

1 0 i J or separate.

Now every auxiliary node must be at a place where some two

paths cross or separate, for every arc carries some minimal path.

- 18
by lemma and if no minimal paths crossed or separated at an

auxiliary node p then there would be only two arcs incident

at p , a possibility ruled out by our original definition of

the networx. Thus if we count the total number of possible

nodes of crossing or separation on all minimal paths, we will

have at least twice the total number of auxiliary nodes n

a since each node is counted on at least 2 paths. Since there

are -|-(n)(n-l) paths P , we have by the above remarks

i J

n

a i i(i)(n)(n-l)(n-l)(n-2)

= in(n-l)

2

(n-2) .

This completes the proof.

It should be noted in passing that this is not quite the best

bound for n , even for general networks satisfying only the

Q

requirements of theorem 10. However, it is sufficient for our

purposes here^

-

.

(l) It has been shown that if N is a (possibly non -planar)

networx with paths between pairs of initial nodes satisfying

the conditions given in the conclusion of theorem 10, then

n < -Jn(n-2) (n

2

-4n+7) . 8 —

- 19 -
Theorem 12. For any given set of initial nodes there exists an

optimal netvorK.

Proof. " """ j For any given number of auxiliary nodes n_ and any ~ a configuration of arcs and assignment of minimal paths, we have

/( N) = S[v ||p -p ||:p ,p €A , i = l,2,...,m} , 1 J & J K 1

where the sum is taken over all arcs A. of the network, p . and

i J p . being the endpoints of A. . Clearly y(N) is a continuous

K. 1

function, for this configuration and path assignment, of the

auxiliary node positions, which in turn vary over the compact set

n

a

C , the topological product of n

& replicates of the convex

hull of the initial nodes. (See lemma 5*) Thus for each configuration and path assignment there is a minimum value for y( N)

But for a fixed n , there is a finite number of ways in which

fi auxiliary and initial nodes can be connected, and hence a finite

number of configurations and path assignments. By theorem 11

there is a finite number of values for n . Hence there exists

an optimal networK.

v

a

The next section will deal with networks on 3 initial nodes

and their various possible forms.

20
4. OPTIMAL NETWORKS FOR 3 POINTS

In this section we shall use the previous results to develop

theorems about the form of optimal networks joining 3 points

in the plane. Since it is clear that the optimal network joining

collinear points is the straight line segment joining them, by

lemma 5, we shall restrict our attention to non-collinear sets

of 3 points

Lemma 13 . Suppose that in an optimal network N on n

points some initial node p^ is of order 1 . Let x be any

point in the arc (line) incident at p . Then the network

N-(xp_^] is optimal for the set of initial nodes {p u {x}

(where (xp^] is the half-open line segment from x to p^),

with demands the same as in the original, except that the demand

from x to any other initial node p . is X .

Proof . If

optimal for

N' is any network other than

U {x} , then

N-(xp

i

] which is

y(n') > y(H-(xp

1

]) ,

since, if y(N') < y (N-(xp ]), then y(N* U (xp^) < y( N),

contradicting the optimality of N . Thus N-(xp^] is optimal

for {p . U {x} . J Jfi

- 21
Lemma Ik. Suppose that N is an optimal network for the

initial nodes 3

• If T is any similarity transformation,

then T(N) is optimal for the set of initial nodes WPj)}

with demands . between T(p_, ) and T(p.) . ij i' ' J

Proof. Let y(

T ) < y(T(ll)) for some Nf , with respect to

the set £t(p

±

)

}

. Then

y(T~~(N ' ) ) = i y(N’) < - y(T(N)) = y(N) ,

where p is the ratio of the transformation T . Thus T ^(N’)

forms a network connecting the points {p^} which gives a lower

value than N for ya contradiction.

Theorem 15 . If each initial node in an optimal network on 3 points

is of order 2, then the network is a triangle connecting the 3

initial nodes.

Proof. Choose minimal paths in the network N to satisfy theorem 10,

Consider any initial node of N , say p^’ . By theorem b, one of

the. two arcs incident at p^ must carry path P and the other

must carry P . By theorem 10, these paths can never meet

after separating at p_ and hence have an intersection of length 0 . Similarly for the pairs of paths P^ and > at ; and P^

and Pp q , at p^ . Thus, since the intersection of any two minimal

paths is of length 0 , we must have

y(K) > 2 (X+X

iJ

)i(P

iJ )

.

- 22
But clearly £ (X+A., ,)4(P. .) is minimized vhen each i(P..) is

- •

-

-1 ) J minimized, which is possible only vhen N is a triangle joining

the 3 initial nodes. This completes the proof.

Theorem 16 . The only topological configurations possible for an

optimal network on 3 nodes are those shown in figure 3*

Proof . We consider networks on three points according to the orders

of their initial nodes. It is clear that each initial node must be

of order > 1 , and by theorem 6 the order must be < 2

First assume all nodes are of order 2. Then by the previous

theorem, we have figure 3s > the triangle.

If two nodes are of order 2 and one of order 1, consider the

new set of nodes formed by deleting the node of order 1, p^ , and

adding the auxiliary node p at the other end of the arc incident

at p, . By lemma 13, the network N-(pp^] must be optimal for

this new set of nodes (with the proper demands). But p is of

order 2, since it was previously of order 3, "by theorem b, and now

has 1 less arc. By the previous theorem, N-(pp^] is therefore a

triangle, and so N is as in 3c.

(Note that P must be an auxiliary node in the above proof,

since if p = p then the resulting networx N-(pp.

is a

J

"L straight line segment, by lemma 5, thereby contradicting the fact

that the other initial node is of order 2).

- 23 -
00

(d)

Figure 3. Illustration for Theorem 16.

- 2b -
Next consider the case where two initial nodes say and

, are of order 1 and the third, p^ , is of order 2. Let p*

be the node at the other end of the arc incident at p^ and

p" the node at the other end of the arc incident at p^ . Form the networx N-(p'p^] - (p’^] . By a double application

of lemma 13 , this new network must be optimal for the set of

points p

! , p

M

, and p^ , with appropriate demands. Now it

may happen that p* = P^ > in vhi ch case it is clear that figure

3f is obtained. Or it may happen that p' , p" , and p^ are all

different, in .which case, by an argument similar to that above,

all are of order 2. Hence N-(p’p^] - (p'^] I s a triangle,

and we get 3&. It is not possible, however, that one of p

l

and p" , say p

’ , is equal to p , while p" ^ p^ . For

then p" is of order 2 in the new network, by theorem 6, but is

of order 1 by lemma 5 • Similarly, p

T ^ p" .

Finally, consider the case where each initial node is of

order 1. If p' , p

M

, and p’" are the nodes at the other end

of the arcs incident at p^ , p^ , and p , respectively, then

either p’ = p" = p" ' or p , p" , and p" ’ are all different,

by an application of lemma 5 and theorem 6 similar to the above.

Thus we get either 3b or 3a . This completes the proof.

- 25 -
The topological configurations for networks given in 3a >

3b , 3c , 3d. , 3e , and 3f will be called suggestively the — 2 A , Y , Y , A , AT , and V configurations. It will be the work

2

of the next two proofs to show that the A is an inessential

configuration, that is, that it need not be considered when looking

for optimal networks

.

Lemma 17 . Given any triangle ABC , with lines BD and (2ET

passing through vertices B and C and the sides opposite them,

respectively (see figure 4), for any point A

r interior to the

triangle and close enough to A , there exist points B' c BD and

C

f € CE such that triangle A’B'C’ is similar to ABC , with

/ \ vertices in the order given. Furthermore, if [A^ is a set

of points interior to ABC , with A^ n ^ -» A , and [A^ n

^B^ n

^C ' j

is a set of triangles satisfying the above statements, then

C . -» B and C^

Proof . Let A* be any point interior to quadrilateral ADFE

(figure 5)* For each point B* e BD define a point f(B ? ) as follows. Draw line A*B’ and construct at A" angle

B’A’G = BAC . Let f (B ! ) be the intersection of a"*G and CE

- .

(if A*G and CE do not intersect, then f(B s ) is not defined.)

Now it Is clear that f(B) exists and is contained in CE , since when B ’ = B line A’G makes a positive angle with respect

to the horizontal (line US). In the same way, it Is clear that

- 26 -
Figure Illustration for Lemma 17

Figure 5* Illustration for Lemma 17*

- 27 -
there is a point B" in BD such that f(BM

) = C , since we may

draw line A’C and then construct an angle at A’ equal to ABC

in a symmetric manner to the above construction.

Now when B

! = B , it is clear that angle A'Bf(B) < ABC . Furthermore, when B* = B" , we have

B*’f (B,! )A* = B”CA 1 < BCA ,

so that, since B^A'C = BAC , we must have A*Bn C > ABC . Now

it is easily shown that f is continuous in B* . Therefore,

there exists some B* lying between B and B” such that

A’B'f (B* ) = ABC .

But this implies that triangle A

t B*f(B ! ) is similar to ABC , and so we choose C* = f(B’) to demonstrate the first part of

the lemma

(n) Next let [A y be a sequence of points in the interior of

ADFE with A^

n ^ -» A . If [B^ j is a corresponding sequence on

(n)

BD' and {C ^

1 "j a corresponding sequence on CE , so that

A^ ; C

V ' is always a triangle similar to ABC , as above,

and if B^V B , the sequence must have a limit point

B

q

f B lying in BD. In fact, we may assume, for convenience,

(n) that B^ — B

q

, since a subsequence converges to B

q

in any event

Now clearly C^

n ^ is continuous in A^ n

^ and . But if

- 28 -
line segment B^A is constructed and an angle constructed at A

equal to BAC , it is apparent that the triangle B^AC^ containing

B A as a side, B AC as an angle, and similar to BAC , has

o o o

’ / \

its vertex C outside BAC . Thus some C' ' must lie outside

o BAC y by continuity of C^

n ^ in A^

n ^ and B^n

^

, and this

(n) contradicts the construction of C^ '

. This proves the second

part of the lemma

2 Theorem 18 . Suppose that a A network is optimal for some 3

points. Then there is a Y network which is optimal for these

3 points.

2

Proof . Let the A network N be as shown in figure 6 .

(Note that lemma 5 implies that the smaller triangle must lie

inside triangle ABC.) By the previous lemma, there exist points

A' , B’ , and C

T on lines JOT , BE" , and CC*' , respectively,

such that triangle A’B’C' is similar to triangle ABC . By the

second part of lemma 17 , these points may be chosen so that

A’CAA" , B’eBB" , and C’eCC" .

. V Let T be a similarity transformation of the plane such that

T(A) = A’ , T(B) = B' , and T(C) = C’ . By lemma 14, T(n) is an

optimal network for the points A’ , B’ , and C

T , with the same

demands as those of A , B , and C respectively.

- 29 -

But so is N-[AA’) - [BB') - [CC') , by repeated applications

of lemma 13* Hence

y(T(N)) = y(h-CaaO-CbbO-Ccc')).

Thus if

N’ = T(N) U AA* U BB’ U CC’ ,

we have

y(N') = y(T(N)) + y(AA' U BB' U CC')

y(N-[M’)-[BB’)-[CC'))

+ y(AA' U BB' U CC')

= y(H) .

(See figure 7-) From this it follows that N' is also an optimal

networK for A,B, and C. But

- 29* -
B

Figure 6. Illustration for Theorem 18.

B

Figure T« Illustration for Theorem 18.

- 30 -
this implies, by lemma 2, that AA , T(AU

) , BB t T(Bm

) } and

CC’T(C M

) are straight angles. Thus we have a new A network

N' where the diameter of the inner triangle has been multiplied

by p < 1 , the ratio of T .

It is clear that by following the same procedure, N* can

be transformed to a network N" in which the diameter of the

2

inner triangle has been multiplied by p , and, in fact, this

process can be continued so that at the m-th step we have a 2 m A network whose inner triangle is of a diameter p times

that of the original. But this implies that line segments AA" , BB

1

' , and CC M

, when extended, meet at some common point 0 , / \

inside triangle ABC . Since y( IT ') = y( N) for each stage,

this implies that the Y network formed by lines AO , BO , and

CO is also optimal. This completes the proof.

From theorem IS it is seen that A networks need not be

considered when looking for an optimal network joining 3 points.

2

This does not mean, of course, that there are no optimal A

networks

The next two lemmas, although applying to the 3-point problem,

are given in a more general setting because of their usefulness

when trying to solve larger networks.

- 31 -
Lenaaa 19 » Let any 3 nodes A , B , and C of an optimal

network be Joined by a Y configuration. If a , b , and c are the respective weight* of the arc# of the Y incident at

A , B , and C and a , fi , and £ are the respective angles

of the Y opposite these arcs, then

cos a * - ,2 2 2 b +c -a 2bc

cos $ = - 2 2,2 a +c -b

2a c

and

cos g

2 2 2

a +b -c 2ab

Proof . From corollary 8 we have that the weights a , b , and c form a triangle. Further, it is obvious that the construction

of the triangle is such that the angle between any two adjacent

sides is the supplement of the angle made by the arcs of the Y

corresponding to those two sides. Suppose that a' , , and

C

1 are the angles opposite sides of length a , b , and c , respectively, in the triangle. By the law of cosines ,

cos a* * *2 2 2

b +c -a

2bc

- 32 -
COS P'

2 2

a +c

2ac

>

and

cos = 2,2 2

a +b -c 2ab

Since a

1 = ff - & , ft' = TT - (3 , and = 17 - C > this completes

the proof.

Lemma 20 . Let any 3 nodes A , B , and C of an optimal

network he Joined by a V conf iguration, where one leg of the V

is AB , the other BC . Let

S = {{i,j} : optimal path P. . A 1

S

Q

= {{i,j} : optimal path P

a = X + EfXjiUjj} € S

A

) ,

b = X + LU^sUjJ] € (SA

-S

C

) U

c = \ + S£A.± j: £i, j} e S

c

) .

c onta ins ABj

contains BC}

( S

C

-S

A

)} ’

)

Then

cos ABC < - 2 2,2

a +c -b

2ac

Proof. Assume cos ABC > - 2 2,2

a +c -b

2ac

It is clear from the

definition of a , b , and c that a+b > c } a+c > b , and

b+c > a y and therefore there exists a triangle with sides

of length a , b , and c . Let

- 33 -
and

a -- cos ,,,22 2 -1 I b +c -a 2b c

$ = cos

Z = cos

-1 / 2 2,2

f a +c -b

l 2ac

, / 2 .2 2

-1 [ a +b -c 2ab

where 0 < a , & , C ,< IT . Then clearly j8 > ABC . Thus

a + C + ABC < 2?f and so we can find a and f such that

S’ + C

= ABC , a + QC < rr

, and £ + £ < tt •

deferring to figure 8, we construct line BO such that

ABO = C > CBO = a . At 0 we construct BOA’ = £ and BOC ’ = a .

It is clear that ATT? must intersect AB , since £ + £ < T , and similarly C'O must intersect EC . Also, it is obvious

that, by choosing 0 close enough to B' we can ma^e A' and

C

! lie in segments AB and BC , respectively. Thus the figure

is as shown.

Now consider the two networks connecting points A’ , B , and

v C': the Y network A

T 0 , BO, and C’O , and the V network

A’B and BC’ . We shall show that the Y gives a smaller value

for y .

It is clear that in the Y network joining A’ , B , and C

1

the weights carried by arcs A’O , BO , and C’O are respectively,

a , b , and c , since all optimal paths going from A* to C*

(or A to C) do not use arc BO . From the proof of lemma J, we

- 34 -
B

Figure 8. Illustration for Lemma 20.

- 35
see that the directional derivative of y in the direction OB

is given by

-b -a cos C -c cos a .

But this derivative i» »ero when 0 is in the position determined

above. Therefore it becomes positive as 0 moves toward B , since both { and ql increase. Therefore, y increases as 0

approaches B . This shows that the Y connecting A' , B ,

C* is not optimal, and hence the Y connecting A , B , and C

cannot be optimal. This completes the proof.

Note that the remarxs following corollary 8 could also have

been used to prove this lemma.

Lemma 20 has an interesting corollary for general optimal

networks, which restricts greatly the possible configurations for

these networxs.

Corollary 21 . If A > V 2-1 , then any optimal network contains

no nodes of order > 3 and no triangles or quadrilaterals. Therefore

every auxiliary node is of order 3 •

Proof . Using the notation of the previous lemma, let a V Join

nodes A , B , and C f with B its vertex , and let

- 36 -
*L

= 2 * S

A

- S

C

} >

Mg = £ {X

i()

: [i,j] c S

c

- SA

} ,

and.

u

3 = S {X

±J

: [i,j] e S

A

n s

c

) .

Then

a = X + ^ + 4 , b = X + ^ + li2 ,

e = X + (Jg + •

By lemma 20,

cos ABC < - 2 2,2

a +c -b

2 ah

(X+/X

l+ 4

3

)

C: + (X+Mg+ fig)2

- (X+/X

L+/ig)

2

2(X+ML+^

3

)(X+M2+M

3

)

2 2

. x + 2jit 3 + 4Afi + 2/^Mj + 2(i2M, - Sj^Ug

2 (X+M1+4

3

)(X+/i2+M

3

)

< - x

2

- 2 ^m2

2(X+jU1

+^

3

)(X+M2+M

3

)

But + fJk^ < 1 - X . Therefore,

2^M2 1 2[^(1-X)]

2

= Kl-X)

2

,

- 37 -
so that

x

2

- 2^ > x

2

- i i-x) 2

> (V2-1)

2

- j(2-«/2)

2

= 0 .

Therefore, cos ABC < 0 , and ABC > - .

This implies that, every V , or meeting of two arcs, has an

77 angle > ^

in an optimal network. Since every angle of a triangle

or quadrilateral defines a V , and since every node defines V's

between each -pair of incident arcs, there can be no triangles or

quadrilaterals and no nodes of order > 3 • This completes the proof.

Next we conqpare the V and the A .

Lemma 22 . Let any 3 nodes A , B , and C of an optimal network

be joined by a V with vertex B . If is as in the proof of

corollary 21 and a’ = ||B-C|| , b’ = || A-C|| , and c' = ||A-B|| , then

X > fJL3

^ a

T +c 1 -b 1 ^ b

1

Proof. Let and also be as defined in corollary 21. If

N is the original network and N* is the network obtained by

adding line AC to N , then tince all minimal paths from B to

C can now travel directly over AC in N* we have

- 3B -
Thus

0 > y(N) - y(N’) > [c * (X+ax1+M

3

) + a ’ ( X+jLl,^) ]

- [c ’ (X+i-i^) + a

! {X+ii^) + b^X+ji^)]

= (a *+c ’ -b ’ )jLl^ - b’X .

V

So far nothing has been said about whether each of the possible

configurations given in theorem lb can actually occur in an optimal

network for some set of initial nodes and some set of X and X. . . ij

The last lemma allows us to construct an A network which is

actually optimal for a set of 3 points and, in fact, is the only

type of optimal network for these points. This implies, by

lemma 13, that there exist optimal Y

? s , Y's , A

f s , and V’s

(where certain demands between pairs are 0 for the Y and V).

Example 23 » There exists an optimal A .

Demonstration . Let initial nodes A , B , and C be the vertices

of a triangle with ||A-B|| = ||A-C|| = 1 , angles BAG = and

' 3

ABC = ACB = % . (See figure 9») Let X = 0.04 and

b

X^b = X^q = X

AC = 0 . 32 . We now show that the optimal network

for A , B , Q nd C is an A network.

First consider the V and the Y as possible networks. Since

* + *AB

* *AC

= ^ + ^AB

+ *BC

^ + *AC

+ ^BC 9 the angles of a Y

" 39 -
o

Figure

9

.

Illustration

for

Example

23.
must all be

19 and 20 . — , or the angle of a V must be >

3

Thus a Y is impossible, since angle

27T 3

by lemmas

BAG = 2!

3

9

and so we consider only the V which, by lemma 20, must have its

vertex at A . But by lemma 22, if a V is optimal then

x - Sc

b'-t-c’-a 1

a

1 9

where a' = ||B-C|| , b

T = || A—c|| , and c* = i'|A-B|| . Since

b ’ = c

’ = 1 , we have a' = V3 9 and so

.04 > .32 = .32 - ij

That is.

But g- = .125 end ^ - 1 = .155

either

Thus a V is not possible

Next consider a A or a Y . Since a A has three initial

nodes of order 2 and a Y has two such nodes, one of B and C

must be a node of order 2 in a ^ or Y . Thus if B, for instance,

is such a node, and ' j3 is the angle made by the arcs incident at B , by lemma 20 we must have

cos 0

< - (/M~Sb^ + (X+A

BC

)2 ~ ( X+XAB

+ Sc

)2

2(A.+A.ab)(X+Abc )

= . (- 36)

2 + (

• 36) 2

- (.68 f ~

i78

2(.3b ) 2

- 41 -
But £ < g- , since ABC = ~ . Thus cos f$ > = .87 , a contradiction.

By theorems 16 and 18, the only other possible configuration

for an optimal network is the A . This finishes the demonstration.

Finally, let us consider a method for actually finding an

optimal network joining any given 3 points. If an electronic

computer is available, this is a very quick procedure, but even

if this is not the case a hand calculation can be done in a reasonable time. The method is to check the actual value of each

of the five possible optimal configurations given in theorem lb

(excluding the A ). For the V and A this is straightforward.

For the Y and Y , the method of locating the auxiliary node

given in [2 ] is very quick, according to the authors. (Of course,

for the Y the procedure is to find a Y connecting the points,

but with demand 0 between the two points which are linked directly.)

The A network is a bit more difficult to find, but a procedure

may be used in which the position of each auxiliary node is alternately optimized, holding the other auxiliary node fixed and

using the method of [ 2 ] . This is done until no further appreciable

movement of either auxiliary node occurs.

As an example of how the angles of an A network might be computed,

we solve for the values of example 23 . (Admittedly, this example is

simplified by its symmetry.)

- K2
Looking at figure 10, where the A network is

outlined in "black with numbers along its various arcs representing

their weights, we see by lemma 19 that angle a must satisfy

cos a - - C,-36)

2

+ (,36)"-(.,68f = ^ _ 2(-36)

2

Thus a = 38 .4°

From this, ft = 180 - 2a = 103*2° . From symmetry, it seems likely

that the two angles represented by y should be equal. Thus

y = |( 120-/3) =8.4° .

The angles represented by 6’s will then be equal, and we have

6 = £( 360 -a) = 160 . 8 °

,

e = 180 - (y+6) = 10 . 8 °

,

C = 30 - f = 19 . 2

° .

That these are the actual angles can be seen by the fact that

that if y and c ere constructed at A and B and at C and B , then the triangles formed are congruent. Thus it is clear that the

middle line of the A is parallel to BC , so that the angles a

are equal in this construction. Since it can be shown that the

positioning of auxiliary nodes is unique for optimality here,

the angles are as given.

- 42a -
o
5 . FURTHER WORK

It is clear that the surface has merely been scratched by

the work here, and that much more remains to be done. Although

optimal networks for 3 points can be found with relative ease, when

n = 4 the problem is much more difficult, and for larger values of

n there is no easy way to find the optimal network, even with a high-speed computer. Of course, if the configuration of the optimal

network and. optimal paths is known, then a generalized version of

the procedure for finding an optimal A networK, given in the

last section, can be used. However, there are a great many

different configurations which can exist.

One direction for more work which seems promising is to group

networks according to the number of cycles they possess (the Betti

number) . The author has found (although it is not proved in this

paper) that the networxs on 3 points with one cycle (the A , Y , and A) are mutually exclus ive in the sense that if one of these

types is optimal then there can be no optimal network of one of the

other types. The same can be said for the V and Y . Thus there

is some hope that a certain exclusiveness might exist among networks

with the same Betti number. Of course, this may prove not to be of

much help anyway, since no general way is known to solve the pure

shortest -network problem (A=l, all A. .=0) on n points, even

J though it is known that the network must be a tree, ([l ])

- 43 -
Another approach is to consider the ways in which optimal paths

split apart, join together, or cross. Theorem 10 states that optimal

paths may always he chosen in such a way that, once two paths

separate, they never again meet. This may give some insight into

possible configurations for an optimal network.
b . REFERENCES

[1] Courant, R. and H. Robbins. What is Mathematics ?,

Nev York, 1941 •

[2] Kuhn, H.W. and R.E. Kuenne, "An Efficient Algorithm for the

Numerical Solution of the Generalized Weber Problem in Spatial

Economics," J. Reg. Sci., Vol. 4, no. 2, 1962.

Ii II [3] Weber, A. liber den Standort der Industrien . Tubingen, 1909*

Translated as Alfred Weber ' s The ory of the Location of

Industries

Chicago, 1929 > C.J. Friedrich.

USCOMM— NBS— DC

- 45 -