# Minimum path cost

A railway has to be built between cities A and B, but a wedge of difficult ground PQR lies between them. Find the best route for the railway.

This problem (from "Mathematician's Delight") can be solved by simply using a ruler and calculating the different costs but which geometrical rule is used in reality?

-
Ask a photon. Small but very clever. – André Nicolas Sep 20 '12 at 19:12
You'd have a graph if you knew the intermediate two points, but even then you know what the path is and what its cost is. Is there some other sort of graph theory beyond the basics that could handle it? All of the graph theory I know seems inapplicable. – rschwieb Sep 20 '12 at 19:23
@André: Ook snel! – Brian M. Scott Sep 20 '12 at 19:24
@AndréNicolas They're always in such a hurry... – rschwieb Sep 20 '12 at 19:26
@rschwieb You are right, I removed that part. – ierax Sep 20 '12 at 19:35

This is a basic constraint optimization problem:

$min$ $c_1 \left\| {X - Y} \right\| + c_2 \left\| {X - A} \right\| + c_2 \left\| {Y - B} \right\|$ (minimize the weighted distances)

Subject to:

$(P - X)\times (X - Q) = 0$

(X must lie on the line between $Q$ and $P$)

and

$(R - Y)\times (Y - Q) = 0$

(Y must lie on the line between $Q$ and $R$)

where $c_1$=20,000 and $c_2$=10,000 $P$, $Q$, $R$ ,$A$, and $B$ are known.

-

Assume that the optimal path has been found.

Draw perpendiculars to $XQ$ and $YQ$; they meet at a point $P$ within the angle $\angle XQY$. Let $M$ be the point of intersection of $PQ$ and $XY$. Snell’s law implies that $\angle PXM=\angle PYM$, so $\triangle PXY$ is isosceles, and $|PX|=|PY|$. It follows that $\triangle PXQ$ is congruent to $\triangle PYQ$ and hence that $XY$ is perpendicular to $PQ$, which bisects $\angle XQY$.

Then $\angle PXQ=\angle PMX=\pi/2$, and $\angle XPQ=\angle MPX$, so $\triangle PXM$ is similar to $\triangle PQX$, and $\angle PXM=\angle XQM$, the half-angle at $Q$.

Extend $AX$ and $BY$ to meet $PQ$ at $R$. Draw a circle $C$ with centre at $X$ and radius $|XP|$, let $U$ be the point where $C$ intersects $AX$, and let $V$ be the point diametrically opposite $P$. Snell’s law also says that $$\sin\angle UXV=2\sin\angle PXM\;.$$

Draw a line through $U$ parallel to $XP$ and a line through $M$ parallel to $XQ$, and let $T$ be their point of intersection. Let $S$ be the point of intersection of $MT$ and $XP$. Then $$\sin\angle PXM=\frac{|MS|}{|XP|}$$ and $$\sin\angle UXV=\frac{|TS|}{|XP|}\;,$$

so $|TS|=2|MS|$. Thus, finding the optimal path reduces to finding $X$ so that when this construction is performed, $|TS|=2|MS|$. The diagram below should help.

This can be accomplished by picking an arbitrary point $X$ on the upper ray from $Q$, drawing a line through it parallel to the bisector $MQ$, and erecting a perpendicular to $MQ$ at $Q$ to meet that line at a point $H$. From $H$ drop a perpendicular to $XQ$, meeting $XQ$ at $I$, and extend it to meet $MQ$ at $J$. Draw a circle $C'$ with centre $H$ and radius $|HJ|$. Let $K$ be the point on $XQ$ such that $|KI|=2|IQ|$. Erect a perpendicular to $XQ$ at $K$, and let $L$ be its point of intersection with $C'$ on the opposite side of $XH$. Now draw a line through $A$ parallel to $LH$; the point at which it meets the upper ray from $Q$ is the desired point $X$. $Y$ is found be dropping a perpendicular from $X$ to the bisector $MQ$ and extending it to meet the lower ray from $Q$ at $Y$. I’ve added this clutter to the figure below.

-