A geometric approach to maximum-speed n-dimensional continuous linear interpolation in rectangular grids
Riccardo Rovatti, Michele Borgatti, R. Guerrieri · IEEE Transactions on Computers · 1998
An algorithm for the linear interpolation of multi-input functions sampled on rectangular grids is presented. A geometric approach is adopted and the mathematics is thoroughly developed. We show that the algorithm is optimum. In fact, when the number n of inputs grows to infinity its computational requirement is O(n log n), which is the same as the lower-bound on the cost of continuous linear interpolation procedures.