# The Weighted Fermat Triangle Problem

Authors: Yujin Shen; Juan Tolosa
Journal: International Journal of Mathematics and Mathematical Sciences
 (2007-10-08)

---

## Abstract

We completely solve thegeneralized Fermat problem: given a triangle P1, P2, P3 and
three positive numbers λ1, λ2, λ3, find a point P for which the sum λ1P1P+λ2P2P+λ3P3P
is minimal. We show that the point always exists and is unique, and indicate necessary
and sufficient conditions for the point to lie inside the triangle. We provide geometric
interpretations of the conditions and briefly indicate a connection with dynamical systems.


---

## Body

## 1. Introduction

Pierre Fermat (1601–1665) formulated the following
problem:Given a triangleABC, find a point P such that the sum of the three distances from P to the vertices
A,B,C be minimal.In the literature, one can find various beautiful ways
to solve the problem (see, e.g., [1–4]). In short, the
answer is as follows. If every angle of ABC measures less
than 120°, then the point P in the interior of the triangle such that ∠APB=∠BPC=∠CPA=120° minimizes the
sum of the three distances. If one of the angles of ABC measures 120° or more, then the vertex corresponding to this angle minimizes the sum of the three distances to the vertices.An important application is theshortest network problem, used in the construction of telephone, pipeline, and roadway networks; see for example [5].In this paper, we consider a weighted Fermat triangle
problem:Given a
triangleP1P2P3
and given three positive numbers λ1, λ2, λ3, find a point P on the triangle such that the weighted sum of the distances to the three vertices λ1P1P+λ2P2P+λ3P3P be the least possible.A possible application is the problem of constructing
a consumer center servicing three given cities in such a way as to minimize the
total distance to all three, but also making the distance to a given city inversely proportional to the population of that city. As we found out after working out a solution, this problem had been previously formulated by
Greenberg and Robertello in 1965  [6] as the three factory problem and solved using trigonometry; two subsequent papers by van de Lindt [7] and Tong and Chua [8] offered geometric solutions. There is also a higher-dimensional generalization in [9]. However, we think our approach is still of interest, firstly, because of the
geometric connections explored throughout the paper, and secondly because of its accessibility. Except possibly for the last section, the paper can be understood by students who have completed the calculus sequence.Using calculus, we obtain necessary and sufficient
conditions forλ1P1P+λ2P2P+λ3P3P to attain its
absolute minimum in the interior of the triangle P1P2P3. We show uniqueness of such minimizing point, and present an elegant geometric construction of this point.In the event that the absolute minimum ofλ1P1P+λ2P2P+λ3P3P does not occur
in the interior of the triangle, we show that one and only one vertex of the
triangle minimizes this sum, and we locate that vertex.In the last section, we briefly show a connection
between the Fermat problem and a gradient dynamical system.


## 2. Existence of a Minimum inside the Triangle

Assuming our plane has Cartesian coordinates(x,y), let Pi have coordinates (xi,yi), i=1,2,3, and let P have
coordinates (x,y). Call di the distance
between Pi and P, i=1,2,3 (see Figure 1).Figure 1Then, the problem is to minimize the function(2.1)f(P)=f(x,y)=λ1d1+λ2d2+λ3d3.This function is continuous on the whole planeℝ2, so it must attain an absolute minimum on the closed
triangle P1P2P3.Let us find the gradient off(P). First of all, we have(2.2)di2=(x−xi)2+(y−yi)2,i=1,2,3,and therefore,
(2.3)∂∂x(di)2=2(x−xi).
If P≠Pi, then di itself is
differentiable, in which case we have(2.4)2di∂∂xdi=2(x−xi).
It follows that
(2.5)∂∂xdi=x−xidi,ifP≠Pi.
Similarly, we get(2.6)∂∂ydi=y−yidi,ifP≠Pi.
Therefore, the gradient ∇di of di is equal to
(2.7)∇di=1di(x−xi,y−yi),ifP≠Pi,wherei=1,2,3.
Let us call
(2.8)ui=∇di=1di(x−xi,y−yi)=1diPiP→.
This is a unit vector, defined for every P≠Pi, i=1,2,3.Getting back to our functionf(P), we conclude that f is
differentiable on the open domain(2.9)Ω=ℝ2∖{P1,P2,P3},
and its gradient is equal to(2.10)∇f=λ1u1+λ2u2+λ3u3onΩ.
Let us see when f can have
stationary points.Lemma 2.1.
A necessary
condition for∇f to be zero (at
some point in Ω) is that
(2.11)λ1<λ2+λ3,λ2<λ3+λ1,λ3<λ1+λ2.
(Geometrically, this means that we can construct a
nondegenerate triangle with sidesλ1, λ2, λ3.)
Indeed,∇f=0 is equivalent
to λ1u1+λ2u2+λ3u3=0. This, in turn, means that the polygonal curve with
sides λ1u1, λ2u2, λ3u3 must be a
triangle; see Figures 2 and 3.
Moreover, in
our case the triangle cannot be degenerate, since this would imply that the
three vectorsu1, u2, u3 are parallel,
which is impossible, for the points P1, P2, P3 do not lie on
one line.
Sinceu1,u2, and u3 are unit
vectors, this triangle has sides λ1, λ2, λ3,
so these three numbers must satisfy the triangle inequalities (2.11).Figure 2Figure 3Lemma 2.2.
If∇f(P)=0 at some P∈Ω, then at this point one has(2.12)u1⋅u2=λ32−λ12−λ22λ1λ2,u2⋅u3=λ12−λ22−λ322λ2λ3,u3⋅u1=λ22−λ12−λ32λ1λ3.
Indeed, if∇f(P)=0, then at P we have(2.13)λ1u1+λ2u2+λ3u3=0.
Let us dot multiply this equality successively byu1, u2, and u3. Recalling that ui⋅ui=∥ui∥2=1, we get(2.14)λ1+λ2u1⋅u2+λ3u1⋅u3=0,λ1u2⋅u1+λ2+λ3u2⋅u3=0,λ1u3⋅u1+λ2u3⋅u2+λ3=0.To simplify matters, let us call for a moment
(2.15)v3=u1⋅u2,v2=u1⋅u3,v1=u2⋅u3.Then, the previous system looks like(2.16)λ1+λ2v3+λ3v2=0,λ1v3+λ2+λ3v1=0,λ1v2+λ2v1+λ3=0.
Let us multiply the first equation by λ1, the second by λ2, and subtract the second from the first:
(2.17)λ12+λ1λ3v2−λ22−λ2λ3v1=0.
This can be rewritten as(2.18)λ1λ3v2−λ2λ3v1=λ22−λ12.
Let us adjoin to this equation the last equation in
(2.16), previously multiplied by λ3 :(2.19)λ1λ3v2−λ2λ3v1=λ22−λ12,λ1λ3v2+λ2λ3v1+λ32=0.Adding both equations in this system, and solving for v2, we get(2.20)v2=λ22−λ12−λ32λ1λ3.
Similarly one gets(2.21)v1=λ12−λ22−λ322λ2λ3,v3=λ32−λ12−λ222λ1λ2.
Our result follows if we recall the notation (2.15).Geometric Interpretation of Equalities (2.12)
Assume that conditions (2.11) hold, so that we can construct the triangle in
Figure 3. Call θi the angle
opposite to the side λi in this
triangle (see Figure 4).
Then, for example,(2.22)u1⋅u2=cos(π−θ3)=−cosθ3
(recall that the ui are unit
vectors), and the first equality in (2.12) follows from the law of the cosine. The
other two equalities in (2.12) have analogous geometric interpretations.Figure 4Lemma 2.3.
IfP lies on one of
the sides of the triangle P1P2P3, but does not coincide with one of the vertices, then ∇f(P)≠0.
Indeed, assume, for example, thatP lies on the
side P1P2 (see Figure 5).
Thenu1 and u2 are parallel.
Moreover, the vectors λ1u1+λ2u2 and λ3u3 are linearly
independent, and at least the second one is nonzero. Therefore,(2.23)∇f(P)=(λ1u1+λ2u2)+λ3u3≠0.Figure 5Lemma 2.4.
IfP lies outside
the triangle P1P2P3, then ∇f(P)≠0.
Indeed, ifP lies outside
this triangle, then it must lie on one of the half-planes whose boundary is the
line joining two vertices, which does not contain the third vertex. Assume, for
example, that P lies on the
half-plane with the boundary through P1P2 which does not
contain P3 (see Figures 6
and 7).
Then, if we draw the vectorsλ1u1, λ2u2, and λ3u3 starting at a
common origin P, all three will lie on the same half-plane with
boundary being the line parallel to P1P2 passing through P. Since all three vectors are nonzero, so is their sum(2.24)λ1u1+λ2u2+λ3u3=∇f(P).Figure 6Figure 7The gradient∇f does not exist
at the vertices of the triangle. However, we can compute one-sided directional
derivatives at these points.Let us start by analyzing the behavior ofd1(P)=d1(x,y) near the
singular point P1. Let us fix an arbitrary unit vector n and a nonzero
number h. Then,(2.25)d1(P1+hn)−d1(P1)h=d1(P1+hn)h=∥hn∥h=|h|h.Therefore,(2.26)Dn+d1(P1)=deflimh→0+d1(P1+hn)−d1(P1)h=1,Dn−d1(P1)=deflimh→0−d1(P1+hn)−d1(P1)h=−1.Let us denote
byαi the angle of
the triangle P1P2P3 at Pi, where i=1,2,3 (see Figure 8).Figure 8Lemma 2.5.
If(2.27)cosα1>λ12−λ22−λ322λ2λ3,then the absolute minimum of the function f(P) given by (2.1) on
the triangle P1P2P3 is not attained at P1.
To show this, let us compute the one-sided directional
derivativeDn+f(P1). Now, only the first term of f(P), that is, λ1d1, is not differentiable at P1; for the other two terms, we can compute the
directional derivative in the usual way. Therefore, we have(2.28)Dn+f(P1)=λ1Dn+d1(P1)+λ2∇d2(P1)⋅n+λ3∇d3(P1)⋅n=λ1+[λ2u2(P1)+λ3u3(P1)]⋅n.The smallest value of this derivative will happen when n is parallel to
the vector λ2u2(P1)+λ3u3(P1) and has the
opposite direction. For such n we get(2.29)Dn+f(P1)=λ1−∥λ2u2(P1)+λ3u3(P1)∥.
Let us denote(2.30)v2=u2(P1),v3=u3(P1);
these are unit vectors directed along the sides P2P1 and P3P1, respectively, as shown in Figure 9. With this
notation, we have
(2.31)Dn+f(P1)=λ1−∥λ2v2+λ3v3∥.
Notice that the vector n we have chosen,
directed opposite to λ2v2+λ3v3, points towards                                                                                                                     the interior of the triangle P1P2P3.
If this derivative is negative, this means that when
we move fromP1 in the
direction of n, the function f(P) will decrease,
so that P1 cannot be a
minimum. For this derivative to be negative, we must have(2.32)∥λ2v2+λ3v3∥2>λ12or(2.33)(λ2v2+λ3v3)⋅(λ2v2+λ3v3)>λ12,or still(2.34)λ22+2λ2λ3v2⋅v3+λ32>λ12.This implies that(2.35)v2⋅v3>λ12−λ22−λ322λ2λ3.Finally, notice that v2⋅v3=cosα1 (see Figure 9).Figure 9In a totally similar way, one can prove that if(2.36)cosα2>λ22−λ32−λ122λ3λ1,
then the absolute minimum f(P) on P1P2P3 cannot be
attained at P2, and if(2.37)cosα3>λ32−λ12−λ222λ1λ2,
then the absolute minimum f(P) on P1P2P3 cannot be
attained at P3.Each of conditions (2.27), (2.36), (2.37) implies the corresponding
one in (2.11) (condition (2.27) implies the first one, etc.). Indeed, assume, for
example, that (2.27) holds. Then, since cosα1<1, we have(2.38)λ12−λ22−λ322λ2λ3<1.This is equivalent to
(2.39)λ12−λ22−λ32<2λ2λ3or(2.40)λ12<λ22+λ32+2λ2λ3=(λ2+λ3)2.Since all λi are positive,
this in turn is equivalent to(2.41)λ1<λ2+λ3.
The other two inequalities are proved in a similar
way.Hence, if (2.27), (2.36), (2.37) hold, we can construct a nondegenerate triangle with sides λ1, λ2, λ3, as in Figure 4. Calling, as before, θi the angle
opposite to λi on this
triangle, and recalling that the cosine function decreases on [0,π], we can rewrite conditions (2.27), (2.36), (2.37) in the following
very natural way:(2.42)αi<π−θi,fori=1,2,3.Lemma 2.6.
Conditions
(2.27), (2.36), (2.37) are necessary for the existence of the absolute minimum of f(P) in the interior
of the triangle P1P2P3.
Indeed, assume, for example, that(2.43)cosα1≤λ12−λ22−λ322λ2λ3.Pick any point P in the interior
of the triangle P1P2P3 (see Figure 10).
Then the angle∠P2PP3 is strictly
bigger than α1. Therefore,(2.44)cosα1>cos∠P2PP3=u2⋅u3,and our assumption implies that(2.45)λ12−λ22−λ322λ2λ3>u2⋅u3.
Then, we cannot have ∇f(P)=0 at this point,
for otherwise we would get a contradiction with the second equality in
(2.12).Figure 10Theorem 2.7.
The functionf(P) attains its
absolute minimum in the interior of the triangle P1P2P3 if, and only
if, conditions (2.27), (2.36), (2.37) hold, or, equivalently, if conditions (2.42) hold.
Indeed, we know, by Lemma2.6, that these conditions are
necessary. Conversely, assume that the conditions hold.
Consider a circleCR, with center anywhere on the triangle, and with a
radius R so large that
the whole triangle lies in its interior and, moreover, on the boundary of CR the minimum of f(P) is larger than,
say, f(P1). (This can be achieved because f(P) tends to
infinity as P tends to
infinity in any direction.)
Now, the continuous functionf(P) must attain a minimum
on the compact set CR. By our choice of R, this minimum is not on the boundary of CR. Further, by Lemma 2.5 and the remark following it,
this minimum is not attained on either vertex P1,P2,P3. Since these are the only singular points of ∇f(P), it follows that the minimum must occur at a point P inside CR at which ∇(P)=0. (This also proves that the gradient                                                                                                                     must vanish somewhere.) By Lemma 2.4, we
conclude that the minimum must lie on the triangle P1P2P3 (vertices
excepted). Therefore, by Lemma 2.3, the minimum must lie in the interior of the
triangle P1P2P3, at a point for which ∇f(P)=0.


## 3. Uniqueness of the Minimum

As in the classical case, the functionf(P) attains its
absolute minimum value exactly at one point.Theorem 3.1.
Assume that
conditions (2.27), (2.36), (2.37) hold. Then f(P) attains its
absolute minimum value in the interior of the triangle P1P2P3 at exactly one
point.
We already know, by Theorem2.7, that f(P) attains its
minimum at some point P inside the
triangle P1P2P3.
Arguing by contradiction, assume that the minimum is
also attained at some other pointP′ inside the
triangle. Then P′ must lie on one
of the triangles PP1P2, PP2P3, or PP3P1 (possibly on
one of the sides PPi). Assume that P lies on PP2P3 as in Figure 11.
Since we have both∇f(P)=0 and ∇f(P′)=0, by Lemma 2.2 we must have(3.1)u2⋅u3=u2′⋅u3′=λ12−λ22−λ322λ2λ3.
On the other hand, we have(3.2)u2⋅u3=cos∠P2PP3,u2′⋅u3′=cos∠P2PP3.
But ∠P2P′P3 is strictly
bigger than ∠P2PP3, so we must have u2′⋅u3′<u2⋅u3, a contradiction.Figure 11


## 4. Construction of the Interior Minimizing Point

Let us assume that conditions (2.27), (2.36), (2.37), or,
equivalently, conditions (2.42), are satisfied. Then, by Theorem 2.7, there is a
point P at which the
function f(P) attains its
minimum; moreover, P lies in the
interior of the triangle P1P2P3. Also, by Theorem 3.1, this point is unique.To actually find the point, we can use a construction
inspired by the one for the classical case (see, e.g., [4]).TakingP1P2 as one of the
sides, let us construct a triangle P1P2P3′, as in Figure 12, which is similar to the triangle in
Figure 4, with sides λ1, λ2, λ3. Moreover, let us choose the angles so that the angle
at P1 is θ1, the angle at P2 is θ2, and the angle at P3′ is θ3. Further, let us draw the circumcircle to this
triangle, and let O be its center.Figure 12The arcP1P3′P2 of this circle
spans the angle θ3, so the complementary arc will span π−θ3.Similarly, let us constructP1P2′P3, also similar to the triangle with sides λ1, λ2, λ3, as in Figure 12, so that the angle at P1 is θ1, the angle at P2′ is θ2, and the angle at P3 is θ3. Let us also draw the circumcircle to P1P2′P3, and let O′ be its center.Now, the formula for the radius of the circumscribed
circle (see, e.g., [1], page 13),
applied to the triangle P1P3′P2, yields(4.1)P1P2sinθ3=2P1O,whenceP1P2P1O=2sinθ3.
Applying the same result to the triangle P1P3P2′, we obtain(4.2)P1P2′sinθ3=2P1O′,whenceP1P2′P1O′=2sinθ3.
We conclude that(4.3)P1P2P1O=P1P2′P1O′.
Hence, the isosceles triangles P1OP2 and P1O′P2′ are similar. Therefore,
the angle ∠OP1P2 is equal to the
angle ∠O′P1P′2. Hence,(4.4)∠OP1O′=∠OP1P2+∠P2P1P3+∠P3P1O′=∠O′P1P′2+α1+∠P3P1O′=α1+θ1.Now, by our assumption (2.42), α1<π−θ1, whence ∠OP1O′<π. This guarantees that, firstly, the two circles are
not tangent, and secondly, the other point P of intersection
of these circles, besides P1, will occur                                                                                                                     inside the triangle P1P2P3. Indeed, from our construction it follows that ∠P2PP1=π−θ3 and ∠P1PP3=π−θ2. Consequently,(4.5)2π−(π−θ2)−(π−θ2)=θ3+θ2=π−θ1,
which is less than π, so P cannot lie
below the line P2P3.We claim thatP is the desired
minimizing point.Indeed, geometrically, the fact that∠P2PP1=π−θ3, ∠P1PP3=π−θ2, and ∠P1PP3=π−θ1 guarantees that
at P one can arrange
the vectors λiui as in Figure 4,
and therefore, (4.6)λ1u1+λ2u2+λ3u3=0,that is, ∇f(P)=0.Here is an algebraic proof of the same fact. AtP, we have(4.7)∥∇f(P)∥2=(λ1u1+λ2u2+λ3u3)⋅(λ1u1+λ2u2+λ3u3)=λ12+λ22+λ32+2λ1λ2u1⋅u2+2λ1λ3u1⋅u3+2λ2λ3u2⋅u3=λ12+λ22+λ32+2λ1λ2cos(π−θ3)+2λ1λ3cos(π−θ2)+2λ2λ3cos(π−θ1)=λ12+λ22+λ32−2λ1λ2cosθ3−2λ1λ3cosθ2−2λ2λ3cosθ1.
Now, by the cosine law,
(4.8)λ12+λ22−2λ1λ2cosθ3=λ32,so the above expression simplifies to(4.9)∥∇f(P)∥2=λ32+λ32−2λ1λ3cosθ2−2λ2λ3cosθ1.Now we add and subtract λ12 and apply the
cosine law twice again:
(4.10)∥∇f(P)∥2=(λ32+λ12−2λ1λ3cosθ2)+λ32−2λ2λ3cosθ1−λ12=(λ22+λ32−2λ2λ3cosθ1)−λ12=λ12−λ12=0.Note. As for
the classical case, it is not hard to show that actually the points P, P3, and P3′ lie on the same
line, and so do the points P, P2, and P2′; this provides another geometric way of constructing the minimizing point P; see [8].
Moreover, generalizing the situation in the classical case, one can see that P3P3′=d/λ3 and P2P2′=d/λ2, where d is the minimum
of our function f(P) (attained at the
point P we just
constructed).


## 5. Degenerate Cases

Case 1.
When one of the triangle inequalities (2.11) fails to
hold then, by Lemma 2.1, the absolute minimum cannot occur in Ω, so it must happen at one of the vertices of our
triangle P1P2P3.Assume, for example, that(5.1)λ1≥λ2+λ3.
Then, we claim that the minimum is attained at P1.Indeed, we have(5.2)f(P2)=λ1P1P2+λ3P2P3≥(λ2+λ3)P1P2+λ3P2P3=λ2P1P2+λ3(P1P2+P2P3).
By the triangle inequality, applied to P1P2P3, we have P1P2+P2P3>P1P3. Therefore, the last expression is strictly greater
than(5.3)λ2P1P2+λ3P1P3=f(P1).
This shows that f(P2)>f(P1). One shows analogously that f(P3)>f(P1).The other two possibilities of failure of (2.11) are
discussed analogously; this leads to the following result.Theorem 5.1.
Ifλ1≥λ2+λ3, then the absolute minimum of f(P) is attained at P1 and only at P1. Similarly, if λ2≥λ1+λ3, the minimum is attained at P2, and if λ3≥λ1+λ2, the minimum is attained at P3.Case 2.
Assume now that the triangle inequalities (2.11) hold,
but one of the conditions (2.42) fails to hold. We claim that only one of these conditions can fail.
Indeed, if we had, say, both(5.4)α1≥π−θ1,α2≥π−θ2,then we would have both(5.5)α1+θ1≥π,α2+θ2≥π.Adding up, we would get
(5.6)(α1+α2)+(θ1+θ2)≥2π,
which is impossible, since α1+α2+α3<π and θ1+θ2+θ3<π. So, only one of the inequalities in (2.42) can fail to
hold.
If we have, for example,(5.7)α1≥π−θ1,
then we will have both α2<π−θ2 and α3<π−θ3. This implies, by Lemma 2.5, the remark following it,
and Theorem 2.7, that the minimum must be attained at P1.
The other two possibilities of failure of (2.11) are
discussed similarly. The following result summarizes our discussion.Theorem 5.2.
If
conditions (2.11) hold and α1≥π−θ1, then the
absolute minimum of f(P) is attained at P1. Similarly, if α2≥π−θ2, then the
minimum is attained at P2, and if α3≥π−θ3, the minimum is
attained at P3.


## 6. The Classical Case

The classical Fermat triangle problem happens when(6.1)λ1=λ2=λ3.
Then, the triangles in Figures 3 and 4 are
equilateral, and therefore(6.2)θ1=θ2=θ3=60°.Also, all the right-hand sides in (2.12) are equal to −1/2. Conditions (2.42) become(6.3)αi<120°fori=1,2,3.
From here one can easily deduce the classical result
stated in the introduction, especially as discussed in [3].


## 7. The Fermat Gradient System

Assume conditions (2.42) hold. As we observed before, the gradient (2.10) of the weighted distance sum f(x,y) given by (2.1) is
defined in all of Ω=ℝ2∖{P1,P2,P3}. Since the function f(x,y) has a global
minimum at the optimal point P, the trajectories in Ω of the gradient
system(7.1)(x˙,y˙)=−∇f(x,y)
will converge to the asymptotically stable equilibrium P. This follows immediately from the fact that V(x,y)=−∥∇f(x,y)∥2 is a global
Lyapunov function for the system on Ω (see,
e.g., [10, Section 9.3]). Moreover, the trajectories of (7.1) are
orthogonal to the level curves of the weighted sum f(x,y).  Figure 13 illustrates the situation for a more
or less randomly chosen triangle, for the                                                                                                                     classical Fermat problem, when all the
weights λi coincide. We
have depicted the direction field of the gradient system plus several
trajectories. The closed lines are the level curves of f.Figure 13Several intriguing questions arise. For example, when
the triangle is equilateral, a single level curve will be tangent to all three
sides as shown in Figure14.Figure 14In general, under which condition(s) is there a level
curve simultaneously tangent to two sides? To all three sides? For a generic triangle, and for thegeneralized Fermat problem, is it always possible to pick the weights λi so that a
single level curve of f will be tangent
to all three sides?



---

*Source: 283846-2008-03-17.xml*