47
$\begingroup$

illustration

There is a river in the shape of an annulus. Outside the annulus there is town "A" and inside there is town "B". One must build a bridge towards the center of the annulus such that the path from A to B crossing the bridge is the shortest possible. Where to build the bridge?

$\endgroup$
9
  • 3
    $\begingroup$ This is a variation of the classical problem where the river is two parallels (a problem that appears in many geometry books, one example is Yaglom's "Geometric Transformations I"). I've been trying to solve this for many days, I have no idea how to justify it, but experimenting with GeoGebra shows that one must join A and B and build the bridge where the segment crosses the external circle, but I don't know how to justify it... $\endgroup$
    – João Rimu
    Oct 12, 2013 at 8:21
  • 8
    $\begingroup$ Unless there's an additional constraint on the bridge, the shortest path is the straight line from A-B, including the bridge. I assume the bridge must be on a radius from the center of the annulus? $\endgroup$
    – Mark Ping
    Oct 12, 2013 at 15:56
  • 17
    $\begingroup$ Just a nitpick: there are no annular rivers. That's a lake you got yourself. $\endgroup$
    – TonyK
    Oct 12, 2013 at 20:33
  • 8
    $\begingroup$ That's a moat!! $\endgroup$ Oct 13, 2013 at 0:12
  • 5
    $\begingroup$ @TonyK Beg to differ: upload.wikimedia.org/wikipedia/en/e/e8/Escher_Waterfall.jpg $\endgroup$
    – Neal
    Oct 13, 2013 at 0:31

4 Answers 4

22
+100
$\begingroup$

To take advantage of Snell's law, applying a limit argument: We want to find the trajectory of a light ray where the velocity on the inner and outer terrain is constant (say $v$) and the velocity on the water ($V$) tends to zero.

Assume first that $0< V \ll v$. Then, calling $R_1$, $R_2$ the inner and outer radius, and $A,B,C,D$ the incidence angles (see figure) we have:

$$\frac{\sin A}{\sin B}=\frac{v}{V}=\frac{\sin D}{\sin C}$$

enter image description here

Now, in the limit $V \to 0$ (which is our scenario) we have $$\frac{\tan B}{\tan C} \to \frac{R_1}{R_2} $$ so, because $\tan B/\tan C \to \sin B/\sin C$, the trajectories must follow the relation:

$$ R_2 \sin A = R_1 \sin D $$

What follows is a bit of trygonometry - straightforward to write, but not to find a closed form equation. I doubt that is feasible, I'd go for a iterative numeric solution, though perhaps this is not much better than simply finding the minimum length numerically. I wonder if there is some geometric construction [*].

Update: I didn't notice that this result is already pointed out in a comment by WimC.

[*] Update 2: A nice geometric interpretation (not exactly a construction) is shown in the figure below. Consider the inner segment from the inner incidence point ($d$) to the target point ($Q$), and extend it until it crosses the outer circle (point $I$). Then, consider the triangle $IdO$ (light blue in the figure), and apply to it the law of sines: $\sin A/R_1 = \sin D/R_2$. For the path to be the optimum one, both angles in the figure ($\alpha$ and $\beta$) must be equal. Click here

enter image description here

BTW: A comment in the question conjectures that "one must join $A$ and $B$ (here $P$ and $Q$) and build the bridge where the segment crosses the external circle". That this is false can be seen easily, (independently of this derivation). Suppose that $L$ is the optimum path (red path) joining $P$ and $Q$, then consider an alternative inner point $Q'$ that lies in $L$, "before" $Q$; then the optimum path must cross the river at the same place. This won't happen if one uses the conjectured construction.

$\endgroup$
12
  • 1
    $\begingroup$ This looks like the right approach to me. $\endgroup$
    – TonyK
    Oct 13, 2013 at 9:47
  • 1
    $\begingroup$ +1. Instead of $B/C$ the ratio $\sin(B)/\sin(C)$ seems more apparent to me from your picture (looking at the slice of annulus between the rays). It would be nice to refer to my comment that already mentioned Snell's law well before you posted your answer. $\endgroup$
    – WimC
    Oct 14, 2013 at 8:13
  • 1
    $\begingroup$ @WimC You're right! Edited. $\endgroup$
    – leonbloy
    Oct 14, 2013 at 12:08
  • $\begingroup$ As I read this it seems to give insight, providing a relationship between $A$ and $D$, but those are still both two unknown quantities. Don't you need a second relation between $A$ and $D$ to solve for them? Maybe it's wrapped up in having that new angle at $\beta$ equal the angle at $\alpha$, but could you add more explaining why these should be equal? $\endgroup$
    – 2'5 9'2
    Oct 15, 2013 at 20:58
  • $\begingroup$ @alex.jordan : $\alpha$ in this figure is angle $A$ in the above derivation. If it's also $\beta$, then you have a triangle with one side $R_1$ (oposite angle $\beta = \alpha = A$) and other side $R_2$ (oposite angle $D$) which satisfies the desired equation $\sin A/R_1 = \sin D/R_2$ $\endgroup$
    – leonbloy
    Oct 15, 2013 at 21:03
18
$\begingroup$

(Edited to make coordinates symmetrical about the $x$-axis from the beginning. Also, notation is changed slightly to help distinguish the path's fixed endpoints from the bridge's variable endpoints.)


Take our path to have fixed endpoints $A(a\cos\phi, a\sin\phi)$, $B(b \cos\phi,-b\sin\phi)$ and our bridge to have to-be-determined endpoints $R(r \cos\theta, r\sin\theta)$, $S(s\cos\theta, s\sin\theta)$ (with $a \geq r\geq s \geq b$). Our goal being to find $\theta$ that minimizes $$|AR|+|RS|+|SB|$$ As $|RS| = r-s$ is constant, we "only" need to minimize $$ p:=|AR|+|SB| =\sqrt{a^2+r^2-2a r \cos\left(\theta-\phi\right)}+\sqrt{b^2+s^2-2bs\cos\left(\theta+\phi\right)}$$ The standard calculus approach is to solve for $\theta$ in the equation $$\frac{dp}{d\theta}=0 \qquad\qquad (1)$$ This is considerably easier said than done, as $(1)$ becomes $$ \frac{a r \sin\left(\theta-\phi\right)}{\sqrt{a^2+r^2-2a r\cos\left(\theta-\phi\right)}} = \frac{bs\sin\left(\theta+\phi\right)}{\sqrt{b^2+s^2-2bs \cos\left(\theta+\phi\right)}} \qquad (2)$$ Squaring and "simplifying" gives a long polynomial in $\sin\theta$ AND $\cos\theta$. Another round of squaring and "simplifying" gets us to a polynomial in $\sin\theta$ OR $\cos\theta$, but it's somewhat less-complicated to express the polynomial equation in terms of complex exponentials: $$\sigma := e^{i\phi} = \cos\phi + i \sin\phi \qquad\qquad \tau := e^{i\theta} = \cos\theta + i \sin\theta$$

And here it is after division by $a^2 r^2 b^2 s^2 \sigma^3$ to highlight some symbolic (and "harmonic") symmetry: $$\begin{align} 0 &= \tau^6 \left( \frac{\sigma}{ar} - \frac{\overline{\sigma}}{bs} \right) + \left( \frac{\overline{\sigma}}{ar} - \frac{\sigma}{bs} \right) \\ &- \tau^5 \left( \frac{\sigma^2}{a^2} + \frac{\sigma^2}{r^2} - \frac{\overline{\sigma}^2}{b^2} -\frac{\overline{\sigma}^2}{s^2} \right) - \tau \left( \frac{\overline{\sigma}^2}{a^2} + \frac{\overline{\sigma}^2}{r^2} - \frac{\sigma^2}{b^2} - \frac{\sigma^2}{s^2} \right) \\ &- \tau^4 \left( \frac{2 \overline{\sigma}-\sigma^3}{ar} - \frac{ 2 \sigma - \overline{\sigma}^3 }{bs} \right) - \tau^2 \left( \frac{2 \sigma-\overline{\sigma}^3}{ar} -\frac{2 \overline{\sigma}-\sigma^3}{bs} \right) \\ &+ 2 \tau^3 \left( \frac{1}{a^2}+\frac{1}{r^2} - \frac{1}{b^2} - \frac{1}{s^2} \right) &(\star) \end{align}$$ A sixth-degree polynomial is, in general, symbolically intractable. Maybe there's some trigonometric structure here that gives rise to a symbolic solution, but this is about as far as I go.

Incidentally, in the case where $A$ lies on the outer bank ---that is, when $a=r$--- the polynomial has a double-root $\tau = \sigma$, corresponding to the condition $\theta = \phi$. This matches our expectation that the bridge must extend directly from $A$. (If the bridge were located anywhere else, then the path from $A$ to $R$ would itself pass through the river.)

Likewise, when $B$ lies on the inner bank, we get a double-root $\tau = \overline{\sigma}$; while this corresponds to having the bridge extend from $B$, it's not as obvious that the bridge must do so. (Unlike the $A$-on-the-bank case, a bridge located elsewhere does not require passing through the river to get from $B$ to $S$.)


@leonbloy's answer leverages Snell's Law. As one expects, his relation is equivalent to equation $(2)$ above. Writing $A^\prime$ and $B^\prime$ for the respective feet of perpendiculars from $A$ and $B$ onto $\overleftrightarrow{RS}$, the Snell equation becomes $$r \sin\angle ARA^\prime = s \sin\angle BSB^\prime$$ whereas equation $(2)$ asserts $$\frac{a r \sin\angle AOR}{|AR|} = \frac{b s \sin\angle BOS}{|BS|} $$ Since $$\begin{align} a \sin\angle AOR &= |AA^\prime| = |AR| \sin\angle ARA^\prime \\ b \sin\angle BOS &= |BB^\prime| = |BS| \sin\angle BSB^\prime \end{align}$$ the equations match.


Separating the $ar$ stuff from the $bs$ stuff in the polynomial $(\star)$ gives $$\left(\tau^2\sigma^2 - 1 \right)^2 \left(\frac{\tau}{a} - \frac{\sigma}{r} \right) \left( \frac{\tau}{r} - \frac{\sigma}{a} \right) = \left( \tau^2-\sigma^2 \right)^2 \left( \frac{\tau \sigma}{b} - \frac{1}{s} \right) \left(\frac{\tau\sigma}{s} - \frac{1}{b} \right) \qquad\quad (\star\star)$$ which seems to be trying to tell us something. Unsurprisingly, $(\star\star)$ can ultimately be manipulated into $(2)$, because $(2)$ is the computational essence of the problem. I'm wondering, though, whether $(\star\star)$ encodes geometric insights that help in understanding this result.

I should probably let this go. :)


One more thing ...

Equation $(2)$ can be interpreted geometrically as $$\frac{|\triangle AOR|}{|AR|} = \frac{|\triangle BOS|}{|BS|}$$

which implies that the altitudes of $\triangle AOR$ and $\triangle BOS$ corresponding to edges $AR$ and $BS$ are congruent. This says exactly that $O$ is equidistant from the (extended) edges, so that those (extended) edges must be tangent to some common circle about the origin. This gives us a strategy for finding the bridge.

Build an auxiliary circle (the purple dashed one) and let $Q$ and $R$ be the points where the tangents to that circle from $A$ meet the outer riverbank (blue circle), and let $S$ and $T$ be the points where the tangents from $B$ meet the inner riverbank (red circle). Build bridges at $Q$ and $R$ (in blue), and $S$ and $T$ (in red). Then, simply adjust the size of the auxiliary circle until a blue bridge overlaps a red bridge.

enter image description here $\qquad$ enter image description here

I think that only two overlaps are ever feasible. (In the diagram, the $T$ bridge never gets close enough to the $Q$ and $R$ bridges ... except in the case of collinear $O$, $A$, $B$ when the auxiliary circle collapses to a point and all bridges coincide.) This seems consistent with a question I posed in a previous edit about whether four of the roots of $(\star)$ are always extraneous.

$\endgroup$
2
  • $\begingroup$ The problem is rotational invariant so you can put A right over the origin. Just a small simplification. $\endgroup$
    – user641
    Oct 13, 2013 at 2:50
  • 2
    $\begingroup$ If you try some nice (say, integer) values for $a$, $b$, $c$, and $d$, and some nice values for $\theta$ ($\pi/2$, $\pi/4$, etc), does the polynomial have roots expressible with radicals or trig expressions? If not, then maybe there is just no hope beyond numerical methods. $\endgroup$
    – 2'5 9'2
    Oct 13, 2013 at 7:40
4
$\begingroup$
  • This can be solved using Calculus.
  • You are given points $A$ and $B$.
  • Let the point $O$ be $(0,0)$ then $C$ is $(a \cos\theta, a \sin\theta)$, $D$ is $(b \cos\theta,b \sin\theta)$. [$a$ is $OC$, $b$ is $OD$]
  • Write the equation for distance between $A$ and $B$, differentiate with respect to $\theta$ and set to $0$. $$|AB|=|AC|+|CD|+|DB|$$
$\endgroup$
13
  • 9
    $\begingroup$ This is totally unhelpful IMHO. $\endgroup$
    – TonyK
    Oct 12, 2013 at 20:24
  • 2
    $\begingroup$ Have you tried it? $\endgroup$
    – TonyK
    Oct 12, 2013 at 20:27
  • 4
    $\begingroup$ When I tried this approach, I found myself with an unwieldy sixth-degree polynomial in $\cos\theta$. Yuck. $\endgroup$
    – Blue
    Oct 12, 2013 at 20:27
  • 4
    $\begingroup$ +1. This problem is very similar tote goat grazing problem. Note that you don't need to include the bridge length, as it's fixed. Instead you have a function of the angle of the inner circle, and you want to minimize it. $\endgroup$
    – user641
    Oct 12, 2013 at 20:52
  • 4
    $\begingroup$ @Bitrex: The problem stipulates that $C$ and $D$ are collinear with $O$: "One must build a bridge towards the center of the annulus ..." $\endgroup$
    – Blue
    Oct 12, 2013 at 22:04
4
$\begingroup$

The problem is equivalent to the famous Alhazen's problem in optics, which was solved geometrically by, among others, Christiaan Huygens:

http://www2.kenyon.edu/Depts/Math/Aydin/Teach/128/AlHazen.pdf

https://en.wikipedia.org/wiki/Alhazen%27s_problem

https://books.google.com/books?id=r-UBPLPyrOcC&pg=PA97

$\endgroup$
7
  • 1
    $\begingroup$ It was solved by Alhazen himself, in Ancient Times. $\endgroup$
    – user366367
    Dec 26, 2017 at 15:40
  • 1
    $\begingroup$ The main reference is "Mathematical Origami: Another View of Alhazen's Optical Problem", by Roger C. Alperin. $\endgroup$
    – user366367
    Dec 26, 2017 at 15:44
  • 1
    $\begingroup$ Where may I find Huygens' solution? $\endgroup$
    – Viktor K.
    Dec 26, 2017 at 15:56
  • 1
    $\begingroup$ @Viktor Kaspervich: At archive.org, I don't know where exactly, but it is there. I am sure, because I took a look at it some years ago and it was too tough for me and so I deleted the file. Sorry, :( $\endgroup$
    – user366367
    Dec 26, 2017 at 16:01
  • 1
    $\begingroup$ Relevant book: amazon.com/Science-without-Numbers-Hartry-Field/dp/0198777922 $\endgroup$
    – user366367
    Dec 26, 2017 at 17:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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