# 1D irregular interpolation with $O(1)$ or $O(\log(N))$ evaluation

In Floater's paper on barycentric rational interpolation, he shows that a stable interpolant using irregularly space points can be evaluated in $O(N)$ operations.

For equally spaces samples, cubic b-splines can be used to generate an interpolator that requires $O(1)$ evaluation, and using the Catmull-Rom curve, $O(\log(N))$ operations can interpolate the curve, but the parameterization cannot be supplied.

Is there an algorithm which creates a $C^1$ interpolant from irregular samples (with user-supplied parameterization) which can be evaluated $O(1)$ or $O(\log(N))$ time?