Search for range in continuous function satisfying some condition

Question

I am attempting to define an optimization for the following problem: given a graph find the largest interval(s) where S > S_th (the narrower the interval the smaller S will be) and P < P_th (the wider the interval the higher P will be).

• I am not 100% certain the claims in parenthesis are always correct as, I think, it is affected by the distance between the Red and Green graphs.

The graphs R and G is KDEs generated with Gaussian functions, therefore continuous.

I already know that the conditions can be true only where the Red graph is above the Green one. I, therefore, find the intersections between the graphs (e.g. with brentq) and find relevant intervals by calculation a single point in them.

Below are a few examples of graphs I want to analyze. The blue vertical lines mark graph intersections; blue horizontal lines with the condition results on top are shown only when the conditions were met for the whole interval.

The vertical and horizontal lines in black are generated from an ML algorithm which I want to replace with a numerical calculation. As it can be seen it, usually, finds intervals that are smaller than the whole area where red is on top.

Example 1: ML algo found the better solution on the right section, neither found the left one interesting.

Example 2: On the right, you can see the ML algo suggesting a range not quite between the blue lines. I am OK with the new algo clipping the portion on the left. Example 3: showing that there may be more than one interesting range per marked section. Example 4: ML algo missed the leftmost range

Answer 1

Let $x_1,x_2,\dots,x_n$ denote the $x$-values where the two curves intersect; you say you know how to find these. Let's add $x_0=-\infty$ and $x_{n+1}=+\infty$. Then in each interval $[x_i,x_{i+1}]$, either the red curve is consistently above the green curve or vice versa, so label that interval with the color of the curve that is on top. This is easy to do by picking an arbitrary $x$-value in $(x_i,x_{i+1})$ evaluating the height of both points at that point.

Now your problem reduces to the following: find $x_i,x_j$ that maximize $x_j-x_i$, such that all of the intervals $[x_i,x_{i+1}],[x_{i+1},x_{i+2}],\dots,[x_{j-1},x_j]$ are labelled red.

This problem can be solved in a straightforward way, in linear time. Iterate through $j:=1,2,\dots,$, scanning from left-to-right, keeping track of the smallest $i$ such that all intervals between $x_i..x_j$ are labelled red. Thus, when you encounter a red interval $[x_{j-1},x_j]$, you do nothing; when you encounter a green interval $[x_{j-1},x_j]$, you reset $i := j$. Keep track of the longest range you've found so far as you do the linear scan.