# How do I interpolate between points so that the interpolation function is injective and smooth?

I have a set of $$n$$ points, $$\left\{ \left(x_i,y_i\right) \right\}$$, where for all $$i$$ (except for $$1$$ and $$n$$), $$x_{i-1} < x_i < x_{i+1}$$ and $$y_{i-1} < y_i < y_{i+1}$$.

What I want to do is to construct a function $$f:[x_1, x_n]\mapsto [y_1, y_n]$$ that

1. satisfies $$f(x_i)=y_i$$ for all $$i$$
2. is injective
3. is at least twice differentiable (but ideally more).

Linear interpolation is not differentiable. Lagrange polynomial or spline interpolation cannot be guaranteed they are injective (usually not). I found one question in this site but I am not sure if this is what I want, given that it is not an interpolation, while mine does not necessarily require it to be a single polynomial over the domain ( Polynomial fitting where polynomial must be monotonically increasing ).

Is there a way to make an interpolation function that is guaranteed to be injective and smooth?

Edit: Thanks to QiaochuYuan's comment, I add another detail. I want this function to have a minimal number of inflexion points. With the worst possible data, it would have $$n-3$$ inflexion points (as lonza leggiera pointed out). So I guess a "good" interpolation should have inflexion points no more than $$n-3$$, or whatever the minimum number of points that data can allow, while being twice differntiable. Specifically, the problem I concern right now only involves 5 points, and it seems possible to have only 1 inflexion point for the given data.

• If this is all you want to do you can start with the linear interpolation, then replace the function at each point, where it looks like a corner, with a smoothed out corner however you like. Whether this is useful for anything depends on what you want this for. Commented Feb 15, 2023 at 1:59
• @QiaochuYuan OK. I think an additional constraint would be the minimal number of inflexion points -- thus requiring the second order derivatives to exist. What I'm dealing with is usually close to a Gaussian cumulative distribution, so only one inflexion point would be ideal. Commented Feb 16, 2023 at 0:45
• It would be impossible to interpolate an injective function through the points unless $\ y_{i+1}=y_i\$ whenever $\ x_{i+1}=x_i\$ and $\ y_{i+1}>y_i\$ whenever $\ x_{i+1}>x_i\$. If your points do satisfy these conditions you might as well eliminate any duplicated $\ x,y\$ pairs so that you have a set of $\ x_i,y_i\$ for which $\ x_i<x_{i+1}\$ and $\ y_i<y_{i+1}\$ for all $\ i=1,2,\dots,n\$. Commented Feb 16, 2023 at 2:37
• @lonzaleggiera Edited as you suggested. Thank you. Commented Feb 16, 2023 at 2:37

$$\def\eqdef{\stackrel{\text{def}}{=}}$$ Not an answer, but a couple of observations that are too long for comments.
• If $$\ f\$$ is twice continuously differentiable then it can be forced by your data to have at least $$\ n-3\$$ inflection points. By the mean value theorem, for each $$\ i=1,2,\dots,n-1\$$ there must exist $$\ \xi_i\in\big(x_i,x_{i+1}\big)\$$ such that $$f'(\xi_i)=\frac{y_{i+1}-y_i}{x_{i+1}-x_i}\ ,$$ and then for each $$\ i=1,2,\dots,n-2\$$, there must exist $$\ \zeta_i\in\big(\xi_i,\xi_{i+1}\big)\$$ such that \begin{align} f''(\zeta_i)&=\frac{f'(\xi_{i+1})-f'(\xi_i)}{\xi_{i+1}-\xi_i}\\ &=\frac{\frac{y_{i+2}-y_{i+1}}{x_{i+2}-x_{i+1}}-\frac{y_{i+1}-y_i}{x_{i+1}-x_i}}{\xi_{i+1}-\xi_i}\ . \end{align} Since $$\ \xi_{i+1}>\xi_i\$$, the sign of $$\ f''(\zeta_i)\$$ is the same as that of $$\ s_i\eqdef\frac{y_{i+2}-y_{i+1}}{x_{i+2}-x_{i+1}}-\frac{y_{i+1}-y_i}{x_{i+1}-x_i}\$$ and so if $$\ s_i\$$ and $$\ s_{i+1}\$$ are of opposite signs then there must be a point of inflection of $$\ f\$$ lying between $$\ \zeta_i\$$ and $$\ \zeta_{i+1}\$$. Therefore, the number of points of inflection that $$\ f\$$ will be forced to have is the number of sign changes in the sequence $$\ s_1,s_2,\dots,s_{n-2}\$$, which will be $$\ n-3\$$ if the signs of $$\ s_i\$$ alternate. For $$\ n=5\$$, therefore, it's possible that $$\ f\$$ could be forced to have at least two inflection points.