Algorithms for computing the optimal Lipschitz constant of interpolants with Lipschitz derivative

One classical measure of the quality of an interpolating function is its Lipschitz constant. In this paper we consider interpolants with additional smoothness requirements, in particular that their derivatives be Lipschitz. We show that such a measure of quality can be easily computed, giving two algorithms, one optimal in the dimension of the data, the other optimal in the number of points to be interpolated.