2

I have a set of points $(x_0,y_0)$ ... $(x_N,y_N)$ with the $x_i$ increasing and the $y_i$ such that $\frac{y_{i+1} - y_{i}}{x_{i+1} - x_{i}} > \frac{y_{i} - y_{i-1}}{x_{i} - x_{i-1}}$

Is there a well-known interpolation scheme that would give me a smooth function $f$ that is continuous, differentiable, and convex?

I don't want to constrain the derivative at the $x_i$, I just want the function to be as smooth as possible without introducing inflexion points. Ideally the derivative should be as smooth as possible as well.

Edit: For instance, in the following charts, I am trying to fit a set of points that are clearly convex. However the kernel interpolation I am performing is not:

enter image description here

d--b
  • 158
  • 7
  • A natural cubic spline will probably be convex "by chance". –  Oct 17 '18 at 09:38
  • This is what splines are for. Check out Bezier curves (quadratic and cubic are most widely used in computer graphics). It works by gluing parabolas/cubic lines according to some condition in the middle, and depending on the choice of constraints (minimal total curvature, continuity of derivatives, etc), you can get what you want. https://en.wikipedia.org/wiki/Spline_interpolation – orion Oct 17 '18 at 09:39
  • @Yves Are splines smooth? I thought they were only $C^2$. – Jam Oct 17 '18 at 09:44
  • @Jam: the OP is asking continuity and differentiability. –  Oct 17 '18 at 09:45
  • @Yves They ask for a smooth $f$ – Jam Oct 17 '18 at 09:46
  • @Jam: all smooth functions are continuous and differentiable, it wouldn't make sense to add the requirements. –  Oct 17 '18 at 09:47
  • A natural cubic spline does not guarantee convexity for convex data. However, I think it should be possible to ensure convexity by constraining the derivatives at the data points --- wait, you said you don't want to do that. Why not? It is the standard approach for the analogous problem of monotone interpolation. –  Oct 17 '18 at 10:09
  • $C^2$ is smooth enough for my requirements – d--b Oct 17 '18 at 11:26
  • @Rahul: constraining the derivatives at the data points (for example with catmull-rom splines) is quite a strong constrain on the shape of the curve. I tried catmull-rom splines anyway, but they did not guarantee convexity... – d--b Oct 17 '18 at 11:34
  • @YvesDaoust: It's true that in many cases, cubic splines will be convex "by chance", but there is no guarantee at all, and for the purpose of my calculation, I need to be absolutely certain that the interpolation is convex. – d--b Oct 17 '18 at 11:48

1 Answers1

1

It looks like Gregory's Shape Preserving Spline Interpolation https://ntrs.nasa.gov/archive/nasa/casi.ntrs.nasa.gov/19850020252.pdf provides a spline that fits the requirements. Strangely it doesn't seem to be implemented in any interpolation packages I found... Maybe it's got a different name...

d--b
  • 158
  • 7