Shortest path inside the rectangle but not in the obstacle between two points

79 Views Asked by At

Given a convex closed curve, a rectangle and two points $A$ and $B$ inside the rectangle but not in the closed curve, I'd like to calculate the shortest path between $A$ and $B$ such that the whole path is inside the rectangle but there is not any part of the path inside the convex curve (intersecting at the convex curve is allowed).

If the segment between $A$ and $B$ does not intersect the convex curve, we can just focus on this segment: if it is inside the rectangle, it must be the shortest path; if not, there must be no other valid path between $A$ and $B$. But the problem is much harder when $AB$ intersects the convex curve.

From $A$, we have two tangents to the curve, so does $B$. Let the points of tangency of $A$ be $A_1$ and $B_2$, and the same for $B_1$ and $B_2$ (WLOG, assume $A_1$ and $B_1$ are at the same side of line $AB$). Therefore, we have two paths between $A$ and $B$, each having two line segments and one segment of curve (i.e., $A-A_1-B_1-B$ and $A-A_2-B_2-B$). If the shortest one is within the rectangle, we are done; if the shortest one does not fit in the rectangle, can we claim that:

1) if the longer one fits, it must be the shortest valid path between $A$ and $B$,

2) if neither fits, there must be no other valid path between $A$ and $B$?