How to fit smooth a curve through min/max intervals

1
votes

I have a list of numeric measurements (see the graph below). Because these measurements are imprecise, each measurement is represented as a pair (min, max), where min (blue) is <= the actual value and max (red) is >= the actual value.

enter image description here

Now I'd like to fit a smooth curve (green) through these min/max pairs. Like bending a strip of flexible material to fit between the min/max pairs. I'm not looking for a continuous function; I'm just interested in the discrete values. That is, I'd like a single smoothed value for each (min, max) pair.

I'm sure there must be an existing algorithm for this. I just can't find it. Splines seem to be the obvious candidate, but I can't figure out how to fit a spline between min/max pairs.

2
algorithmsplinesmoothing
This seems to be a pretty difficult problem. – Yves Daoust
With the "strip of flexible material" analogy you can apply structural civil engineering concepts. It's a beam supported in some of the min values and loaded with max values, which blend the strip. Setting the supports is easy. Solving the deformations can be done by elements connections (a matrix matter) and solving the equations or with more grained finite elements method (FEM). Too large to explain here. – Ripi2
@Ripi2: "Setting the supports is easy": I doubt it, you don't know on what side to support, if any. The number of possibilities is huge. The challenge is not in solving the elasticity equations, this is simulated with a spline (IMO, even a thin plate spline is overkill, natural cubic is enough). The difficulty is combinatorial. – Yves Daoust

2 Answers

0
votes

There is a brute force solution that works as follows:

  • for every abscissa, choose one of three options

    1. the curve goes through the min value,

    2. the curve goes through the max value,

    3. the curve is free and doesn't use this abscissa.

  • when you have performed all assignments, compute the cubic spline through the selected points.

  • check that the curve does not infringe a min/max constraint at an unused abscissa.

  • for the remaining valid curves, compute a merit figure such as an estimate of the total curvature.

Keep the solution that achieves the lowest total curvature.

This is only feasible for a small number of abscissas. In the given example, you should try 3^10=59049 solutions !

Maybe the complexity can be reduced by working with an increasing number of abscissas and keeping partial solutions, but this doesn't seem to be rigorous.

Notice that when you add points on a side of a cubic spline, the whole curve is influenced. But the influence goes diminishing as you move away, and the chances of infringing a constraint should be low.

Another line of attack could be with B-splines, which have the attractive property that new points only influence the curve in a close neighborhood.

0
votes

I dont't know if this is a real solution, but I think it's at least a good start point towards the solution.

First detect "true" points that the solution pass through:

A "blue" point i is "true" if point[i].min > point[j].max && point[i].min > point[k].max
with lastRedTrue < j < i and k > i

A "red" point i is "true" if point[i].max < point[j].min && point[i].max < point[k].min
with lastBlueTrue < j < i and k > i

In your example, we'll get points 3(min), 5(max) and 9(min)

Perhaps a correction is needed when two consecutive "true" blue's or red's are found.

Next, start point. The idea is

if firstBlue > firstRed
    startWith = blue
else
    startWith = red

and similar way for end point. This idea may be adjusted for a few cases.

The intermediate "true" points are discovered when a line true[i] to true[i+1] does not pass between point.min and point.max. I mean, both point.min and point.max lie in the same side of that line, and thus point is also "true".
In the example, new true points are 2(max) and 7(max)

The rest of the points must be tested not with a straight, but with the curve passing through true-points.

The final solution may need more tests due to some point losing its "true" feature because now the line between adjacents is curved instead of straight.