4
$\begingroup$

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.

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?

  • 0
    @faif You didn't have to remove that... I was just offering feedback :)2012-09-20

2 Answers 2

2

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.

1

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.

enter image description here

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.

enter image description here