Cool. You may want to add more interpolants, for instance a Fourier (for regularly spaced points) or (even better, but not regularly spaced) Chebyshev interpolation would be useful, highly accurate, and can be computed fast (N log(N))
I definitely want to add more interpolants. The only limitation really is that it has to be possible to do the calculation lazily. As I understand Fourier interpolation, this should be fine with that. I am less familiar with Chebyshev interpolation.
For Fourier, given an N-dim vector you would compute the N Fourier coefficients in Nlog(N) time, stored in memory, then whenever a new x-value is requested it takes linear time to evaluate the point (add up the basis vectors with the stored coefficients).
Chebyshev polynomials are more accurate than Fourier. In fact they are the most accurate interpolating polynomials in general. They're not as wildly known, but often used in numerical analysis. The problem with Fourier is that if your function is not periodic, the coefficients do not converge quickly, making the interpolant less accurate for a given number of nodes. Chebyshev gets around this problem, but instead of using equally spaced points, points are spaced out along the uneven "Chebyshev nodes". So to get an interpolated point, say 2.5, 2.5 no longer falls halfway between the 2nd and 3rd Cheb node, you would first have to figure out the value of 2.5 in the nonuniform Chebyshev distribution of points, and then compute the interpolating value in linear time at this point.[1]
Both Chebyshev and Fourier are "global" interpolants. As opposed to cubic splines and your other ones. If you change a single value in your vector, the entire interpolant is affected and needs to be recomputed.
> For Fourier, given an N-dim vector you would compute the N Fourier coefficients in Nlog(N) time
But Nlog(N) only works for certain values of N, right (like powers of two)? I guess for other cases, we could use the clipping method to dictate behavior, but that doesn't feel great.
