Is there a better than O(N*W) algorithm for calculating the sliding window maximum slope to a point at fixed X position in the window?

Given two series H[t], F[t], and a window size W; the objective is to find a third series M[t], such that M[t] is the maximum of all slopes from point (t-1, H[t-1]) to points (t..t+W, F[t+W]).

Graphical example (note that H[t] is not shown, only its Y intercept H[t=0]):
Plot.
The value of M[t=0] is the slope of the blue line.

The purpose of this is to generate a sort of 'loose' signal envelope. In this application, H[t-1] is in fact dependent on the value of M[t-1] in the previous window, but the specifics are external to this algorithm. More importantly: it is an on-line process, data beyond the window is not accessible, and it requires giving the answer immediately for each window.

The brute force approach O(N*K), that is, evaluating the slope for every sample (F[t..t+W]) for every window, might not be appropriate for this application (window size is in the realm of 2k-20k samples, real-time requirements)

At first I thought it could be solved almost identically to the rolling maximum problem, with a deque. I eventually found that varying H[t] does not preserve the total order of the slopes (consider any two samples, if H[t] changes 'sides' relative to the line formed by the two samples, their maximum slope relation is reversed), and thus the deque becomes corrupted.

Yet another problem with that kind of approach is that, while that algorithm is in a whole O(N) (O(1) per window on average), it can have O(W) 'jitter' for certain windows that have to 'purge' a full deque (in fairness, that probably has a small enough constant to be acceptable).

The next approach I'm trying is to keep a BST of the sample's values (which can be kept updated for O(log(W)) per window) and somehow use it (along some other data structure or mathematical property) to discard most of the slope calculations, but it seems to be a dead end (Fast X and Y search does not imply fast Y/X lookup).

As an aside, does this problem has a less verbose name? I hope I managed to get the point across.

Let's consider a block-based algorithm first.

Give H[0...W-1] and F[1...2W], we can calculate M[0...W-1] in O(W log W) time.

This will let you solve your whole problem in O(N * log W) time, but in a streaming audio context, that means introducing a 2W-sample delay or so. If that will do the job for you, then great! If not, we can discuss a tricky way to reduce that after.

The key to the block-based algorithm is that the maximum slope from any H-point into its target F-window is always on the upper convex hull of the F-window. If you have the convex hull for an F-window, you can find the target for any H-point by binary search, because the slope of the convex hull is monotonically decreasing. If a guessed F-point is too early, then the following segment of the convex hull will point back underneath the H-point. If the guessed F-point is late enough, then it's either the last point, or the following segment will point back at or over the H-point.

So to start use the monotone chain algorithm, scanning forward, to compute the upper convex hull of the F-points from F[W] to F[2W]. In the process you will get the upper convex hulls of all the prefixes of that window. Each prefix is the tail-end of the target window for exactly one H-point. Set the H-value to the maximum slope to a point in it's tail-end window.

Then use the monotone chain algorithm again, this time scanning backward, to compute the upper convex hull of all the F-points from F[W-1] to F[1]. During this process you'll get the upper convex hulls of all the suffixes of that window. Each suffix is the remaining part of the target window for the immediately preceding H-point. Calculate the maximum slope from the H-point, and save it if it's bigger than the one you already have.

When you're done, you have the final slopes for each H-point.