# Homework Help: The Art and Craft of Problem Solving, 1.3.4

1. Apr 5, 2008

### PFStudent

The Art and Craft of Problem Solving, 2nd Edition
By: Paul Zeitz

1. The problem statement, all variables and given/known data

1.3.4
In the xy-plane, what is the length of the shortest path from $$(0,0)$$ to $$(12, 16)$$ that does not go inside the circle ${{(x - 6)}^{2}} + {{(y - 8)}^{2}} = {25}$.

2. Relevant equations

Standard form of the Equation of a Circle.

$${{(x - h)}^{2}} + {{(y - k)}^{2}} = {{r}^{2}}$$

Standard form of the distance between two points $$({x}_{1}, {y}_{1})$$ and $$({x}_{2}, {y}_{2})$$ in the xy-plane.

$${d} = {\sqrt {{{{\left({x}_{2}} - {{x}_{1}}\right)}^{2}} + {{\left({{y}_{2}} - {{y}_{1}}\right)}^{2}}}}$$

3. The attempt at a solution

$${P}_{m} \equiv$$ midpoint
$${d} \equiv$$ the distance between $$({x}_{1}, {y}_{1})$$ and $$({x}_{2}, {y}_{2})$$
$${d}_{r} \equiv$$ diameter
$${{D}_{min}} \equiv$$ the length of the shortest path between $$({x}_{1}, {y}_{1})$$ and $$({x}_{2}, {y}_{2})$$ that does not go inside the circle, $${{(x - 6)}^{2}} + {{(y - 8)}^{2}} = {25}$$.
$${C} \equiv$$ circumference of the circle.

$$({x}_{1}, {y}_{1}) = (0, 0)$$
$$({x}_{2}, {y}_{2}) = (12, 16)$$
$$(h, k) = (6, 8)$$
$${r} = 5$$

Let, $$Ax + By = C$$ be the equation of the line between $$({x}_{1}, {y}_{1})$$ and $$({x}_{2}, {y}_{2})$$.

Note, that $$h$$ and $$k$$ in this problem are half of ${x}_{2}$ and ${y}_{2}$, additionally since $$({x}_{1}, {y}_{1}) = (0, 0)$$ the point $$(h, k)$$ is the $${P}_{m}$$ of the line $$Ax + By = C$$. Furthermore, this means that the length between $$({x}_{1}, {y}_{1})$$ and $$({x}_{2}, {y}_{2})$$ that goes inside the circle is the diameter. Lastly, this implies that the shortest length to avoid the inside of the circle is half of the circumference of the circle.

So, this problem is then simplified to finding the below,

$${D}_{min} = {{d} - {{d}_{r}} + {\frac{C}{2}}}$$

Which is,

$${{D}_{min}} = {\left({\sqrt{{{\left({{x}_{2}}-{{x}_{1}}\right)}^{2}}+{{\left({{y}_{2}}-{{y}_{1}}\right)}^{2}}}}\right)}-{\left(2r\right)}+{\left(\frac{(2{\pi}{r})}{2}\right)}$$

$${{D}_{min}} = {{\sqrt{{{\left({{x}_{2}}-{{x}_{1}}\right)}^{2}}+{{\left({{y}_{2}}-{{y}_{1}}\right)}^{2}}}}}+{r\left({\pi}-2\right)}$$

$${{D}_{min}} = {10+5{\pi}}$$

In addition, how would one solve a generalized form of this problem,

In the xy-plane, what is the length of the shortest path from $$({x}_{1}, {y}_{1})$$ to $$({x}_{2}, {y}_{2})$$ that does not go inside the circle ${{(x-h)}^{2}}+{{(y-k)}^{2}} = {{r}^{2}}$.

I tried figuring out the above but did not know how to approach the case if the circle was not "in the way" so to speak of the shortest length between the two points. How is it that one can apply constraints to this problem to tell whether the circle: would be or would not be in the way?

Thanks,

-PFStudent

Last edited: Apr 5, 2008
2. Apr 5, 2008

### HallsofIvy

I would hope that it is obvious that if the circle is not "in the way", then the shortest distance between two points is a straight line! The circle is "in the way" if and only if the straigth line between the two points crosses the circle.

3. Apr 5, 2008

### PFStudent

Hey,

Thanks for the reply HallsofIvy. Yes I did see that obvious conclusion, :-). However, how is it that using the two points and (h, k) that one can determine whether or not the line will go through the circle. In other words, what intervals can I use to determine whether I am dealing with a line that does not go through the circle or one that does.

Thanks,

-PFStudent

4. Apr 5, 2008

### HallsofIvy

I would hope that it is obvious that if the circle is not "in the way", then the shortest distance between two points is a straight line! The circle is "in the way" if and only if the straigth line between the two points crosses the circle.

5. Apr 6, 2008

### montoyas7940

What would be a good method for solving this considering a circle that is "in the way" ?

6. Apr 6, 2008

### durt

Consider any of the points on the circle that you can get to by following a straight path from the starting point. Clearly any shortest path that contains any of these points will also contain a line segment from it to the starting point. Your attempt, however, fails this requirement.

7. Apr 6, 2008

### Dick

Given that the circle is 'in the way' the closest path will meet the circle on a tangent line from each endpoint. Do you see why?

8. Apr 6, 2008

### montoyas7940

I sure would like to find out how a problem like this is solved but I don't want to hijack pfstudents thread. What do you suggest?

9. Apr 6, 2008

### Dick

There are a very small number of paths that intersect the circle at a tangent. Once you've figured out where the four tangent points are, there should be only two paths that suggest themselves as shortest. Then just test each one and see which one actually is. There's nothing very systematic about this approach, it's basically just 'drawing a picture'.

10. Apr 6, 2008

### montoyas7940

What I imagine is that there is a rubber band stretched between the two points and a r5 circle centered at (6,8) is pushing it to the side. It seems that there would be two tangents and one arc length that I would have to add. What I don't know is how to calculate the tangents. I found a tutorial for a circle centered at the origin but this one is not.

11. Apr 6, 2008

### Dick

Then move the coordinates so the center of the circle is at (0,0). That shifts your endpoints to (-6,-8) and (6,8). Now the circle is centered at the origin.

12. Apr 6, 2008

### montoyas7940

LOL, Ok maybe the hard way some other time then.

13. Apr 6, 2008

### Dick

There's no magic answer. You really do have to find the tangent points.

14. Apr 6, 2008

### montoyas7940

I understand, finding the tangents with the circle centered at other than the origin is what I don't know how to do. I will work on it some other time.
Thanks for looking at it. Good night.

15. Apr 7, 2008

In this case it is simple to see whether the line segment intersects the circle; compare the line connecting the origin to (12,16) and the line connecting the origin to the center of the circle.

16. Apr 16, 2008

### PFStudent

Hey,

In looking over the generalised problem I proposed--essentially it comes down to four scenarios.

Scenario Ia:
If the line does not intersect the circle at any point, then the shorest distance is merely the distance between point 1 and point 2.

Scenario Ib:
Say that the line intersects the circle at exactly one point, then the shortest distance between point 1 and point 2 is still just the distance between the two points. In other words, the line is tangent to the circle (at exactly one point).

Scenario II:
The next easiest scenario is say the line intersects the circle at two points (say Point A and Point B) such that the distance between the two points (A and B) is the diameter of the circle.

Scenario III:
This scenario is say the line intersects the circle at two points (say Point A and Point B) such that the distance between the two points (A and B) is a chord.

Scenario IVa:
Say that one of the two points is chosen in the set of points contained inside of the circle but not on the circle--essentially the problem you then have is impossible to solve since there is no (real) path between the two points such that the path does not go inside of the circle.

Scenario IVb:
Say that both of the two points are chosen such that they are both inside of the set of points contained inside of the circle but not on the circle--again this problem is unsolvable as well since there is no (real) path such that the path does not go inside of the circle.

Overall, solving this generalised problem comes down to determining which scenario your dealing with, that being said did I cover all the possible scenarios?

Thanks,

-PFStudent

Last edited: Apr 16, 2008
17. Apr 16, 2008

### Dick

WAY too many cases. As I said in post 7, any path that hits the circle nontangentially is automatically suboptimal and doesn't need to be considered.

18. Apr 16, 2008

### PFStudent

Hey,

If I understand your posts correctly, the interpretation of the problem that you pose is the following: that the shortest path between two points that does not go inside the circle is a path tangent to the circle between the two points. Is that right?

Ok, so essentially then your minimizing what the shortest distance between the two points is assuming that the two points can be placed anywhere...

I interpreted the problem as asking for a more comprehensive solution--such that given any placement of the two points how would one determine the shortest path between those two points.

Is my interpretation wrong then?

Thanks,

-PFStudent

Last edited: Apr 16, 2008
19. Apr 16, 2008

### Dick

My point is that if you draw a path that hits the circle nontangentially, goes around the circle and the proceeds to the other point, then that path is longer than another path that hits the circle tangentially. Draw some examples.

20. Apr 16, 2008

Hey,