Given two points P, Q on the same side of a line l, find the point X which minimises the sum of the distances from X to P, Q and l.
Solution
wlog take P to the right of Q and Q to be closer to the line than P. Take A on the line so that PA makes a 30o angle with the line and A is to the left of P. Similarly, take B on the line so that QB makes a 30o angle with the line and B is to the right of Q. There are three cases to consider.
(1) If the two segments PA and QB intersect, then their point of intersection X is the required point.
(2) If A is to the right of B, then join P to Q' the reflection of Q in the line. X is the point at which PQ' meets the line.
(3) If PA and QB do not meet, but A is to the left of B, then take X = Q.
We must now prove these statements. It is convenient to take the line l to be the x-axis. Take Q to be (a, b) and P to be (c, d). We assume that d > b > 0. Notice first that the sum of the three distances from the point X with coordinates (x, y) , which we will write as f(x, y), is a continuous and differentiable function of x and y. Also it tends to infinity as x or y tends to infinity. Hence the minimum must occur either (A) at a point where grad f = 0, or (B) on the boundary of the allowed region, in other words on y = 0, or (C) at a point where grad f does not exist.
We have f(x, y) = y + √( (x - a)2 + (y - b)2) + √( (x - c)2 + (y - d)2). Hence grad f = ( (x - a)/QX + (x - c)/PX, 1 + (y - b)/QX + (y - d)/PX) = r + q + p, where r is the unit vector along the perpendicular line from the line l to X, q is the unit vector from Q to X, and p is the unit vector from P to X. By resolving along the line perpendicular to r we find that the angles between q and r and between p and r must be equal. Similarly, the other pairs of angles. Hence the angle between each pair of p, q, r is 120o. But it is clear that the only possible such point is the intersection H of the segments PA and QB (if it exists). H is thus the only candidate of type (A).
It is obvious that for points X on the line l, f(x, y) is minimised at K, the intersection of the line with PQ' (joining P to the reflection of Q), so that is the only candidate of type (B). Finally, the only points were the existence of grad f is doubtful are P and Q and indeed it is easy to see that grad f is not well defined there (for example, the limits as we approach parallel to the two axes are different). But clearly the distance sum is lower at Q than at P, so Q is the only candidate of type (C).
We now look separately at cases (1), (2) and (3). In case (1) all three candidates H, K and Q are available. We show first that H is better than Q. Let the perpendicular from Q to l meet l at C and the perpendicular from H to l meet l at D. Then angle HQC is 60o, so QC = HD + QH/2. By the cosine rule we have PQ2 = PH2 + QH2 + PH·QH > (PH + QH/2)2. Hence PQ + QH/2 > PH + QH and so PQ + QC = PQ + QH/2 + HD > PH + QH + HD. Next we show that H is better than K. As before let HD be the perpendicular to l. It is sufficient to show that PH + QH + HD < PD + QD, since we know that PD + QD <= PK + QK. Now PD2 = PH2 + HD2 + PH·HD > (PH + HD/2)2, so PD > PH + HD/2. Similarly, QD > QH + HD/2. Adding gives the required result. That shows that H minimises the distance sum for case (1).
In case (2) only candidates K and Q are available. Take QC and PE as the perpendiculars to l. Then PQ2 = CE2 + (PE - QC)2, PQ'2 = CE2 + (PE + QC)2. We wish to show that PQ' < PQ + QC, or CE2 + (PE + QC)2 < CE2 + (PE - QC)2 + QC2 + 2 QC √(CE2 + (PE - QC)2), or (4 PE - QC)2 < 4(CE2 + PE2 - 2 PE QC + QC2), or 4 CE2 > 12 PE2 - 3 QC2. That is certainly true since we have CE > (PE + QC) √3.
Finally, in case (3) the only candidates are K and Q. So as in the previous paragraph we wish to show that 4 CE2 < 12 PE2 - 3 QC2. Now we have CE < √3 (PE - QC) from which the inequality follows.
This is a messy problem. It is fairly well known that in the general case one wants 120 deg angles and that for points on a line one looks at the straight line to the reflection, so it is fairly clear what the solution is. But there are lots of messy details.
© John Scholes
jscholes@kalva.demon.co.uk
15 Feb 2002