# Monotonicity preserving interpolant in 1D

I have a dataset $$\{x_i, y_i\}_{i=0}^{n-1}$$ where $$x_0 < x_1 < \cdots x_{n-1}$$ (not uniformly spaced), and, in addition $$y_0 < y_1 < \cdots y_{n-1}$$. So it feels natural to assume that $$y_i$$ are samples of an unknown monotonically increasing function.

I would like to interpolate these data, but it is very important that the interpolant be monotonically increasing. Obviously linear interpolation satisfies my requirements, but is there something smoother, with constant time or $$O(\log(n))$$ evaluation?

• First of all, cause your data points are monotic in both x and y, that doesn't mean they are unknown samples of unknown monotonically increasing function. I hope you know it. By the way, There are countless smooth and monotonic functions that could be fitted precisely into your data. For example you have n data points and a (n-1)th-degree polynomial will be perfectly fitted on your data, but so what?! it's not correct to choose the regression function solely based on its mathematical properties. If you have a theory, that theory should tell you what regression function should be at the end. – Alone Programmer Sep 26 at 13:38
• @AloneProgrammer: Note that I am not asking for a regression function, but an interpolator. – user14717 Sep 26 at 13:53

Piecewise Cubic Hermite Interpolating Polynomial (PCHIP) preserves monotonicity and has continuous derivatives. It can be evaluated in $$O(\log(n))$$.