6
$\begingroup$

Hallo everybody,

I have the following problem regarding shortest paths in $R^2$.

Suppose you are given two points $p$ and $q$ and two unit disks, as in the picture. I am looking for a path from $p$ to $q$ through a point $c_1$ in the first disk and $c_2$ in the second disk such that the sum $\overline{p c_1}+\overline{c_1 c_2}+\overline{c_2 q}$ is minimum.

I know how to find a path if there is only one disk, via reflection properties of ellipses. However, the case for two disks eludes me. I was hoping that you could have some suggestions, or some pointers to something to read.

Thanks in advance for your answers.

$\endgroup$
3
  • $\begingroup$ Do you really mean a point in the disk, or in the circle? $\endgroup$
    – Jack M
    Aug 28, 2014 at 13:19
  • $\begingroup$ I mean closed disk, that is, inside and on the boundary. Not that you want to put anything inside anyway! $\endgroup$
    – ichfarbstift
    Aug 28, 2014 at 13:23
  • $\begingroup$ Sounds like the funicular polygon in engineering statics. If $O_1,O_2 $ are centers of the circles, forces applied through $c_1O_1,c_2 O_2 $ should be angular bisector of each string at $O_1,O_2. $ $\endgroup$
    – Narasimham
    Aug 25, 2015 at 23:59

2 Answers 2

Reset to default
0
$\begingroup$

Let's name the circles $S_1,S_2$ so that $c_i \in S_i$. Using calculus you can prove that if the minimum is achieved with the configuration that you have shown then at each of the two points $c_i$, the two angles of incidence must be equal, meaning the angles that the two arcs make with the circle $S_i$ at the point $c_i$.

$\endgroup$
2
  • $\begingroup$ Yes, ok. But is there a way to compute these points directly? I am a computer scientist and would need this as a subroutine inside an algorihtm. Life would be easier if I could claim that these points can be computed in constant time! $\endgroup$
    – ichfarbstift
    Aug 28, 2014 at 13:25
  • $\begingroup$ Newton's method would probably work really well. $\endgroup$
    – Lee Mosher
    Aug 28, 2014 at 17:21
0
$\begingroup$

I will elaborate Narasimham' comment :

Consider the case where $c_1$ is fixed. If center of cicle containing point $c_i$ is $O_i$, then the minimum is attained when $Oc_2$ bisects the angle $\angle c_1c_2q $.

Now assume that $c_i$ are movable : For some $c_i$ if minimum of total length $|pc_1|+|c_1c_2|+|c_2q|$ is obtained and if we assume that there are not two bisections, then we can assume that there is no bisection at a point $c_2$. Then we fixes $c_1$ and we move $c_2$ so that there is bisection. Hence we have length decreasing which is a contradiction. Hence minimum of total length can happen when there are two bisections.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .