Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
3  
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. –  faif Sep 20 '12 at 19:35
show 1 more comment

2 Answers 2

up vote 2 down vote accepted

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.

share|improve this answer
add comment

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.