Maximum distance between a line segment and a polygon Given a (non-convex) Polygon $P$ and a straight line segment $S$ in $\mathbb{R}^2$, where $S$  and $P$ are disjoint, I am looking for an efficient algorithm to find a point $s$ on $S$ which has the maximum distance from $P$ among all points on $S$ (and the actual distance, which is then trivial, of course). 

To be clear, the distance $dist(s,P)$ between one point $s$ and $P$ is the minimum distance between $s$ and all points in $P$ (which I can calculate by a standard point-to-polygon algorithm). So another way to write this formally is:

"Determine $max(min(|p-s| : p \in P) : s \in S)$ (and the related points)".

Note the point of maximum distance can be somewhere in the middle of $S$:



I have checked some standard resources (including this site) and books from computational geometry, but had no luck so far. If $S$ is described as a parametric curve $c(t)$ where $t \in [0,1]$, this is the problem of finding the global maximum of $dist(c(t),P)$ in $[0,1]$, so it would even help me if someone has an idea how to split $[0,1]$ into subintervals where each subinterval contains only a local maximum. That would allow me to apply a standard numerical maximum search algorithm to each of the subintervals.

Any ideas?
Hint:

If I am right, the Euclidean distance map to a polygon is made of planar and conic patches (along edges and around vertices respectively). Their construction is analogue to that of the Voronoi diagram of the polygon. (But strangely, the case of the Voronoi diagram on the outside of a filled polygon seems to never have been addressed.)

The case of a convex polygon is easy. That of a concave one, much less.

If you project the line segment S onto this map, you will traverse line segments and hyperbolas. As the concavity is downward, the searched maximum will occur either at the intersection of patches or at the segment endpoints.

Could be solved with a version of Fortune's sweepline algorithm, adapted to polygons, if that exists...
Edit: Since the poster clarified himself, the below is irrelevant to his new formulation of the problem. I'll leave it since it solves the old formulation: $\max_{s \in S}{\max_{p \in P}{d(s,p)}}$.

Measure all distances between the polygon's vertices and the line segment's endpoints, pick the maximum. The algorithm works in $O(V)$, there cannot be a faster one since you need to at least iterate over the vertices to get the correct answer.