Processing math: 100%

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 ¯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 θ. However, I found it easier to work instead with the central angle θ. We might as well parameterize the path by the point of incidence x and write the length as:

f(x)=|¯ax|+|¯xb|.

Now, what do we know about each of ¯ax and ¯xb? Assume da and db are the distances from c to a and b, respectively. Let's look at cxa. By the law of cosines, we have that:

|¯ax|2=d2a+r22darcosθ.
Likewise for cxb, where ϕ=acb, we get:
|¯xb|2=d2b+r22dbrcos(ϕθ).

It's quite disappointing that we don't obtain nice expressions for |¯ax| and |¯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)=|¯ax|2+|¯xb|2.

We can then write the derivative as:

f(x)θ=12|¯ax|2|¯ax|2θ+12|¯xb|2.|¯xb|2θ.

Plugging in |¯ax|2θ=2darsinθ and |¯xb|2θ=2dbrsin(ϕθ) we get:

f(x)θ=darsinθ|¯ax|dbrsin(ϕθ)|¯xb|.

Setting f(x)θ=0, cancelling r and rearranging, we find that:

dasinθ|¯ax|=dbsin(ϕθ)|¯xb|.

It would really help to realize that dasinθ=|¯aa| and dbsin(ϕθ)=|¯bb|, where a and b are the projections of a and b, respectively, on cx. Making this substitution we get:

|¯aa||¯ax|=|¯bb||¯xb|.

Letting ϕ=axb, this is the same as:

sinθ=sin(ϕθ).

Or,

θ=ϕθ.

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 α=cax and β=cbx. Applying the law of sines in cxa and cxb we find that:

sin(πθ)=sinθ=darsinα,sin(ϕθ)=dbrsinβ.

Since the point x we are interested in makes θ=ϕθ, we get:

dasinα=dbsinβ.

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 abx. Letting α=cab and β=cba we can write:

(αα)+(ββ)+ϕ=π.

Rewriting ϕ=2θ and rearranging we get:

β=(α+βπ)α+2θ.

Noting that θ=arcsin(darsinα), we can now eliminate β using the first equation to get an equation for α only, and the same can be written for β:

α=(α+βπ)+2arcsin(darsinα)arcsin(dadbsinα).

Other than a numerical approach, it is plausible to assume α is small especially when dar. This might justify linearizing both the sines and arcsines to get something like:

αα+βπ1+dadb2dar.