Given a direction vector and an arbitrary polygon (which can be non-convex), what is an efficient algorithm to find the longest straight line along the vector bounded by the polygon?
note: the original problem which is somewhat related to the one above is: given a triangle, find the largest bounded similar triangle within a given polygon.
Here's an O(n log n)-time sweep-line algorithm for your first problem (the "original" looks rather more difficult).
Assume without loss of generality that the vector is (1, 0). Assume no degeneracy (this is slightly naughtier of me). For each edge of the polygon, create a "start" event for the vertex with lesser y-coordinate and a "stop" event for the vertex with greater. Sort the events by y-coordinate and process them from least to greatest. For a start event, insert the edge into a sorted set keyed by the x-coordinate of the intersection of the edge with the current sweep line. For a stop event, remove the edge. Just before and just after operating on the set, check whether the segment of the sweep-line joining the two edges at the insertion/deletion point is longer than the longest found so far. (It's possible to tell whether the segment is inside the polygon by whether these two edges, traversed in counterclockwise order with respect to the polygon, are y-increasing or y-decreasing.)
