Interpolation advice (linear, cubic?)

I need to find good approximations of the points where an undefined function intersect a threshold value. I'm stepping through my space and whenever I find that two subsequent steps are on different sides of the threshold, I add a point somewhere in between:

_{(source: ning.com)}

My first approach was to just pick the mid-point, but this is obviously a terrible solution:

_{(source: ning.com)}

I'm now using linear interpolation which gives a reasonable result, but the underlying function will practically never be linear. Thus, this only works well if my stepsize is small enough:

_{(source: ning.com)}

Sampling the base function can be quite expensive, but adding one or two additional samples in order to get a much better approximation is something I'd like to try. Is it possible to use Cubic interpolation here? Like so:

_{(source: ning.com)}

Or are there better ways?

Much obliged, David Rutten

ps. I'm writing in C#, but this is a language agnostic problem.

Your last picture shows only three points, which only suffice to define a quadratic polynomial, not cubic. For cubic interpolation, you'll need four points. A cubic polynomial can be fitted in different ways; here are two.

The most straightforward way is to simply let the (unique) polynomial pass through all four points.

Another way is to use tangents. Again, we need four points. Let the left two points define a slope. Have the polynomial pass through the second point (in general, it doesn't pass through the first point), and match the computed slope in that point. And same on the right side for the fourth and third point.

By the way, any higher-order polynomial is probably a bad idea, because they tend to become very unstable in the presence of even a little bit of input noise.

If you give some more details about your problem domain, I might be able to give a more specific answer. For example, where do your data points come from, what kind of curve can you generally expect, and can you go back and sample more if required? I can provide equations and pseudo-code too, if needed.

Update: silly me left a sentence referring to two ways without typing them out. Typed them out now.