Sunday, November 29, 2015

Shortest path touching a circle

This came up a week or so ago in a discussion with a lab mate. The governing principle is well-known from physics, but I was too lazy to find a derivation online. Later on, I had an idea and wanted to give it a try, so here goes.

We're interested in the shortest path starting at point $a$ to point $b$ with the requirement that it intersects a circle of radius $r$ centered at point $c$, and does so before stopping at $b$. When the circle intersects the line segment $\overline{ab}$, the segment coincides with the shortest path. Hence, we are interested in paths that reflect off the circle, just like a ray of light does when it hits a shiny surface. I'll be referring to the figure to the right.

Eventually, we're interested in a statement involving the angle of incidence $\theta$. However, I found it easier to work instead with the central angle $\theta'$. We might as well parameterize the path by the point of incidence $x$ and write the length as:

\[ f(x) = |\overline{ax}| + |\overline{xb}|. \]

Now, what do we know about each of $\overline{ax}$ and $\overline{xb}$? Assume $d_a$ and $d_b$ are the distances from $c$ to $a$ and $b$, respectively. Let's look at $\triangle{cxa}$. By the law of cosines, we have that:

\[ |\overline{ax}|^2 = d_a^2 + r^2 - 2  d_a  r  \cos{\theta'}. \]
Likewise for $\triangle{cxb}$, where $\phi' = \angle{acb}$, we get:
\[ |\overline{xb}|^2 = d_b^2 + r^2 - 2  d_b  r  \cos{(\phi' - \theta')}. \]

It's quite disappointing that we don't obtain nice expressions for $|\overline{ax}|$ and $|\overline{xb}|$ to plug into $f(x)$. But, since we're only interested in minimizing $f$, we might hope that finding the derivative will get us around that. Let's start by rewriting $f$ as:

\[ f(x) = \sqrt{|\overline{ax}|^2} + \sqrt{|\overline{xb}|^2}. \]

We can then write the derivative as:

\[ \frac{\partial f(x)}{\partial \theta'} = \frac{1}{2\sqrt{|\overline{ax}|^2} }\frac{\partial |\overline{ax}|^2}{\partial \theta'} + \frac{1}{2\sqrt{|\overline{xb}|^2}.}\frac{\partial |\overline{xb}|^2}{\partial \theta'}. \]

Plugging in $\frac{\partial |\overline{ax}|^2}{\partial \theta'} = 2d_ar\sin{\theta'}$ and $\frac{\partial |\overline{xb}|^2}{\partial \theta'} = -2d_br\sin{(\phi'-\theta')}$ we get:

\[ \frac{\partial f(x)}{\partial \theta'} = \frac{d_ar\sin{\theta'}}{|\overline{ax}|} - \frac{d_br\sin{(\phi' - \theta')}}{|\overline{xb}|}. \]

Setting $\frac{\partial f(x)}{\partial \theta'} = 0$, cancelling $r$ and rearranging, we find that:

\[ \frac{d_a\sin{\theta'}}{|\overline{ax}|} = \frac{d_b\sin{(\phi' - \theta')}}{|\overline{xb}|}. \]

It would really help to realize that $d_a\sin{\theta'} = |\overline{aa'}|$ and $d_b\sin{(\phi'-\theta')} = |\overline{bb'}|$, where $a'$ and $b'$ are the projections of $a$ and $b$, respectively, on $\overrightarrow{cx}$. Making this substitution we get:

\[ \frac{|\overline{aa'}|}{|\overline{ax}|} = \frac{|\overline{bb'}|}{|\overline{xb}|}. \]

Letting $\phi = \angle axb$, this is the same as:

\[ \sin{\theta} = \sin{(\phi - \theta)}. \]


\[ \theta = \phi - \theta. \]

Which says that the angle of incidence should be equal to the angle of reflection, for the path to be optimal. Which is already known.

Update 01/14/16: There remains the issue of determining the point $x$ that minimizes the shortest path defined by $f$. I found it easier to work with angles $\alpha = \angle{cax}$ and $\beta = \angle{cbx}$. Applying the law of sines in $\triangle{cxa}$ and $\triangle{cxb}$ we find that:

\[ \sin{(\pi - \theta)} = \sin{\theta} = \frac{d_a}{r}\sin{\alpha}, \quad \sin{(\phi - \theta)} = \frac{d_b}{r}\sin{\beta}.\]

Since the point $x$ we are interested in makes $\theta = \phi - \theta$, we get:

\[ d_a\sin{\alpha} = d_b\sin{\beta}. \]

In a way, this equation only describes the angle of incidence from $a$ or $b$ to points on the circle. We still need a second equation to ensure these two angles correspond to a single point of incidence. This can be achieved by examining $\triangle{abx}$. Letting $\alpha' = \angle{cab}$ and $\beta' = \angle{cba}$ we can write:

\[ (\alpha' - \alpha) + (\beta' - \beta) + \phi = \pi. \]

Rewriting $\phi = 2 \theta$ and rearranging we get:

\[ \beta = (\alpha' + \beta' - \pi) - \alpha + 2\theta. \]

Noting that $\theta = \arcsin{(\frac{d_a}{r}\sin{\alpha})}$, we can now eliminate $\beta$ using the first equation to get an equation for $\alpha$ only, and the same can be written for $\beta$:

\[ \alpha = (\alpha' + \beta' - \pi) + 2 \arcsin{(\frac{d_a}{r}\sin{\alpha})} - \arcsin{(\frac{d_a}{d_b}\sin{\alpha)}}. \]

Other than a numerical approach, it is plausible to assume $\alpha$ is small especially when $d_a \gg r$. This might justify linearizing both the sines and arcsines to get something like:

\[ \alpha \approx \frac{\alpha' + \beta' - \pi}{1 + \frac{d_a}{d_b} - 2 \frac{d_a}{r}}. \]