Longest straight line in a convex polygon with fixed slope and constrained endpoints

Question

Consider two convex polygons A and B. Polygon B lies completely inside polygon A. I am trying to find the longest line segment (with a fixed slope) such that:

• One end of the line segment lies on the boundary of polygon B, and the other end of the line segment lies on the boundary of polygon A.

Can anyone help me with an algorithm to find that length?

Further, can this be extended to the following:

• Suppose you have two line segments with different slopes (both fixed slopes), such that they have the same endpoint on or inside polygon B and their other endpoints (would be different for the two lines) on the boundary of A. How would I maximize the sum of their lengths?
• Polytopes/ polygons of higher dimensions?

Answer 1

First, you need to realize that the connecting line segment will never end in the middle of both A's and B's edges.

If it did, and A's and B's edges are not parallel, then moving one way or the other would always result in a longer connecting line segment. If A's and B's edges are parallel, you can move both ways to find equal-length connecting line segments, until you reach a vertex, so there will always be a max-length solution that ends in a vertex.

This reduces the list of potential connecting line segments to line segments that end at a vertex.

So, for every vertex of A, find the (up to) two points on a line of the given slope that crosses B, and choose the point furthest away (if any). That is a candidate line segment.

Do the same for every vertex of B, locating point where line crosses A.

Now select the longest line segment from all those candidates.

Note that the above will work for concave polygons too. There will just be more than two points where a line from the vertex of one polygon crosses an edge of the other polygon.