STEINER’S PROBLEM - MAXIMA AND MINIMA - What Is Mathematics? An Elementary Approach to Ideas and Methods, 2nd Edition (1996)

What Is Mathematics? An Elementary Approach to Ideas and Methods, 2nd Edition (1996)

CHAPTER VII. MAXIMA AND MINIMA

§5. STEINER’S PROBLEM

1. Problem and Solution

A very simple but instructive problem was treated by Jacob Steiner, the famous representative of geometry at the University of Berlin in the early nineteenth century. Three villages A, B, C are to be joined by a system of roads of minimum total length. Mathematically, three points A, B, Care given in a plane, and a fourth point P in the plane is sought so that the sum a + b + c shall be a minimum, where a, b, c denote the three distances from P to A, B, C respectively. The answer to the problem is: If in the triangle ABC all angles are less than 120°, then P is the point from which each of the three sides, AB, BC, CA, subtends an angle of 120°. If, however, an angle of ABC, e.g. the angle at C, is equal to or larger than 120°, then the point P coincides with the vertex C.

image

Fig. 208. Least sum of distances to three points.

It is an easy matter to obtain this solution if we use our previous results concerning extrema. Suppose P is the required minimum point. There are these alternatives: either P coincides with one of the vertices A, B, C, or P differs from these vertices. In the first case it is clear that P must be the vertex of the largest angle C of ABC, because the sum CA + CB is less than any other sum of two sides of the triangle ABC. Thus, to complete the proof of our statement, we must analyze the second case. Let K be the circle with radius c around C. Then P must be the point on K such thatPA + PB is a minimum. If A and B are outside of K, as in Figure 209, then, according to the result in §1, PA and PB must form equal angles with the circle K and hence with the radius PC, which is perpendicular to K. Since the same reasoning applies also to the position of P and the circle with the radius a around A, it follows that all three angles formed by PA, PB, PC are equal, and consequently equal to 120°, as stated. This reasoning was based on the assumption that A and B are both outside of K, which remains to be proved. Now, if at least one of the points A and B, say A, were on or inside K, then, since P, as assumed, is not identical with A or B, we should have a + bAB. But ACc, since A is not outside K. Hence

image

Fig. 209.

a + b + cAB + AC,

which means that we should obtain the shortest sum of distances if P coincided with A, contrary to our assumption. This proves that A and B are both outside the circle K. The corresponding fact is similarly proved for the other combinations: B, C with respect to a circle of radius a about A, and A, C with respect to a circle of radius b about B.

2. Analysis of the Alternatives

To test which of the two alternatives for the point P actually occurs we must examine the construction of P. To find P, we merely draw the circles K1, K2 on which two of the sides, say AC and BC, subtend ares of 120°. Then AC will subtend 120° from any point on the shorter are into which AC divides K1, but will subtend 60° from any point on the longer arc. The intersection of the two shorter arcs, provided such an intersection exists, gives the required point P, for not only will AC and BC subtend 120° at P, but AB will also, the sum of the three angles being 360°.

It is clear from Figure 210 that if no angle of triangle ABC is greater than 120°, then the two shorter arcs intersect inside the triangle. On the other hand, if one angle, C, of triangle ABC is greater than 120°, then the two shorter arcs of K1 and K2 fail to intersect, as is shown in

image

Fig. 210.

image

Fig. 211.

Figure 211. In this case there is no point P from which all three sides subtend 120°. However, K1 and K2 determine at their intersection a point P′ from which AC and BC subtend angles of 60° each, while the side AB opposite the obtuse angle subtends 120°.

For a triangle ABC having an angle greater than 120° there is, then, no point at which each side subtends 120°. Hence the minimum point P must coincide with a vertex, since that was shown to be the only other alternative, and this must be the vertex at the obtuse angle. If, on the other hand, all the angles of a triangle are less than 120°, we have seen that a point P can be constructed from which each side subtends 120°. But to complete the proof of our theorem we have yet to show that a + b + c will actually be less here than if P coincided with any vertex, for we have only shown that P gives a minimum if the smallest total length is not attained at one of the vertices. Accordingly, we must show that a + b+ c is smaller than the sum of any two sides, say AB + AC. To do this, extend BP and project A on this line, obtaining a point D (Fig. 212). Since imageAPD= 60°, the length of the projection PD is image. Now BD is the projection of AB on the line through B and P, and consequently BD < AB. But image, therefore b + image < AB. In exactly the same way, by projecting A on the extension of PC, we see that image. Adding, we obtain the inequality a + b + c < AB + AC. Since we already know that if the minimum point is not one of the vertices it must be P, it follows finally that P is actually the point at which a + b + c is a minimum.

image

Fig. 212

3. A Complementary Problem

The formal methods of mathematics sometimes reach out beyond one’s original intention. For example, if the angle at C is greater than 120° the procedure of geometrical construction produces, instead of the solution P (which in this case is the point C itself) another point P′, from which the larger side AB of the triangle ABC appears under an angle of 120°, and the two smaller sides under the angle of 60°. Certainly P′ does not solve our minimum problem, but we may suspect that it has some relation to it. The answer is that P′ solves the following problem: to minimize the expression a + bc. The proof is entirely analogous to that given above for a + b + c, based on the results of §1, Article 5, and is left as an exercise for the reader. Combined with the preceding result, we have the theorem:

image

Fig. 213. a + b – c = minimum.

If the angles of a triangle ABC are all less than 120°, then the sum of the distances a, b, c from any point to A, B, C, respectively, is least at that point where each side of the triangle subtends an angle of 120°, and a + b – c is least at vertex C; if one angle, say C, is greater than 120°, then a + b + c is least at C, and a + bc is least at that point where the two shorter sides of the triangle subtend angles of 60° and the longest side subtends an angle of 120°.

Thus, of the two minimum problems, one is always solved by the circle construction and the other by a vertex. For imageC = 120° the two solutions of each problem, and indeed the solutions of the two problems, coincide, since the point obtained by the construction is then precisely the vertex C.

4. Remarks and Exercises

If from a point P inside an equilateral triangle UVW we drop three perpendicular lines PA, PB, PC as shown in Figure 214, then A, B, C, and P form the figure studied above. This remark can serve in solving Steiner’s problem by starting with the points A, B, C and then finding U, V, W.

image

Fig. 214. Another proof of Steiner’s solution.

Exercises: 1) Carry out this scheme, using the fact that from any point in an equilateral triangle the sum of the three perpendicular segments is constant and equal to the altitude.

2) Using the corresponding fact when P is outside UVW, discuss the complementary problem.

In three dimensions one might study a similar problem: Given four points A, B, C, D; to find a fifth point P such that a + b + c + d is a minimum.

* Exercise: Investigate this problem and its complementary problem by the methods of §1, or by using a regular tetrahedron.

5. Generalization to the Street Network Problem

In Steiner’s problem three fixed points A, B, C are given. It is natural to generalize this problem to the case of n given points, A1, A2, · · ·, An; we ask for the point P in the plane for which the sum of the distances a1 + a2 +... + an is a minimum, where ai is the distance PAi. (For four points, arranged as in Fig. 215, the point P is the point of intersection of the diagonals of the quadrilateral A1A2A3A4; the reader may prove this as an exercise.) This problem, which was also treated by Steiner, does not lead to interesting results. It is one of the superficial generalizations not infrequently found in mathematical literature. To find the really significant extension of Steiner’s problem we must abandon the search for a single point P. Instead, we look for the “street network” of shortest total length. Mathematically expressed: Given n points, A1, · · ·, An to find a connected system of straight line segments of shortest total length such that any two of the given points can be joined by a polygon consisting of segments of the system.

image

Fig. 215. Least sum of distances to four points.

The appearance of the solution will, of course, depend on the arrangement of the given points. The reader may with profit study the subject on the basis of the solution to Steiner’s problem. We shall content ourselves here with pointing out the answer in the typical cases shown in Figures 216-8. In the first case the solution consists of five segments with two multiple intersections where three segments meet at angles of 120°. In the second case the solution contains three multiple intersections. If the points are differently arranged, figures such as these may not be possible. One or more of the multiple intersections may degenerate and be replaced by one or more of the given points, as in the third case.

image

Figs. 216-8. Shortest networks joining more than 3 points.

In the case of n given points, there will be at most n – 2 multiple intersections, at each of which three segments meet at angles of 120°.

The solution of the problem is not always uniquely determined. For four points A, B, C, D forming a square we have the two equivalent solutions shown in Figures 219-20. If the points A1, A2, · · ·, An are the vertices of a simple polygon with sufficiently flat angles, then the polygon itself will give the minimum.

image

Figs. 219-20. Two shortest networks joining 4 points.