Given a point $P$ and a polyline $L$, you can compute the distance from $P$ to $L$ (i.e., the distance from $P$ to the nearest point on $L$).
Now take the union of all of the following points:
The endpoints of the line segments in the blue polyline
For each endpoint of each line segment in the red polyline, the closest point on the blue polyline
All intersection points where the blue polyline intersects the red polyline
This set can be computed efficiently, and its size is linear in the size of the input. Let $P_1,P_2,\dots,P_n$ denote these points, in the order they appear on the blue polyline. Let $Q_i$ be the point on the red polyline that is closest to $P_i$.
Now consider any pair of consecutive points $P_i,P_{i+1}$. As we move along the blue polyline from $P_i$ to $P_{i+1}$, the distance to the red polyline will either increase monotonically or decrease monotonically. Thus, if it crosses the threshold (e.g., starts below the threshold and increases to something larger than the threshold), you can use binary search to find the point where it crosses the threshold.
In fact, we can say more. Consider a point $P = \alpha P_1 + (1-\alpha) P_{i+1}$, as $\alpha$ increases from $0$ to $1$, and let $Q$ be the nearest point on the red polyline to $P$. As $\alpha$ increases from $0$ to $1$, $P$ be moving along a straight-line path, i.e., along a single line segment of the blue polyline. Similarly, $Q$ will also e moving along a straight-line path, i.e., along a single line segment of the red polyline. Consequently, there's a simple formula for the distance between the two as a function of $\alpha$, and we can solve for the $\alpha$ that makes this distance equal to the threshold. Thus, this will let us precisely identify the point where the minimum distance between the two polylines is exactly equal to the threshold.
Now doing a linear scan over all consecutive pairs $P_i,P_{i+1}$ will enable you to find all places where the minimum distance is higher than some threshold, exactly.
