I am going to assume that we have arrays of the edges representing the top and bottom curves for the winding polygon with edges going from left to right. Also make $n$ as the total number of edges in this polygon. Now consider the following visualization of the geometry where we construct some point using the two "sides" of the concave polygon:
It is clear if we shoot any ray from the point, given the direction is any convex combination of the directions to the two "sides" of the polygon, then the ray will intersect exactly two edges. Let us assume there exists some helper method that can take two line segments and return the maximum distance between them.
If you want a deterministic algorithm, here is one idea using ideas based on the assumptions and ray stuff described above. Suppose we fix some edge $e = (v_1, v_2)$ from the top boundary. We can look at all edges from the bottom boundary that have at least one vertex between the rays drawn to the two vertices of $e$ and compute the maximum distance between them and $e$, using this result to update the overall maximum width for the polygon. If we fan over the polygon from left to right, we can do all of this work in $O(n)$ time since as we check a new edge on the top boundary, we can pick up where we left off in the bottom boundary instead of starting from scratch. Below is a visual of how things get partitioned
Given the earlier assumptions, the following Monte Carlo styled randomized algorithm could also be a solution:
input (top_boundary[...], bottom_boundary[...], k)
init max_width = 0
for i from 1 to k
- randomly choose an edge e from (say) the top boundary (can do this with or without replacement)
- use binary search to find first edge in the bottom boundary, denoted e1, that intersects ray going through left vertex of e
- iterate over all edges from left to right, starting with e1, that have at least one vertex between the rays generated by the left and right vertices of e
- for each edge, compute the maximum width between this edge and e using helper method and update the max_width accordingly
The runtime of the above algorithm using sampling with replacement is $O(k (\log(n) + c))$ where $c$ corresponds to the average number of edges in the bottom boundary that intersect rays that intersect an edge in the top boundary. The probability of failure corresponds to the probability that you never select the edge on the top boundary that corresponds to the maximum width. This error probability shrinks as $k$ gets large and if you randomly choose edges with replacement, $k = O(n)$ gives a constant probability result, implying the runtime is $O(n \log(n) + n c)$. But if the shapes are generally as "nice" as we see in the example, you may be able to get decent approximations (especially compared to the bounding box approach) making $k$ sublinear in $n$, which would make the algorithm as a whole potentially sublinear in $n$, depending on the value of $c$.
If you hate the constant $c$, you could modify this algorithm to randomly construct a ray with a direction randomly chosen between the directions corresponding to the two "sides". You would then, for each random ray, find the two intersecting edges and then compute the maximum width between these two edges. If you use $k$ random rays, this algorithm then gives an $O(k \log(n))$ runtime. With a large enough $k$, you should get a decent estimate, though the error probability could be larger compared to the above algorithm. Again, if shapes are "nice" generally, choosing $k$ to be sublinear in $n$ could be enough to get a decent result in practice, implying an overall sublinear randomized algorithm.
In fact, for the example drawn in the original question, a single sample would prove to be much more accurate than using the bounding box approach, which would give us an $O(\log(n))$ approximation algorithm.