This paper describes an algorithm for the multivariate interpolation of data that may be sparse and unstructured. The main difficulty with this type of problem is the quick determination of a representation of data that is accurate and can be efficiently evaluated. The method proposed is a further modification of the modified quadratic Shepard method (MQSM). The MQSM uses a sum of locally defined quadratic polynomials to represent the data. The quadratic associated with a given data point is constructed using only those data whose coordinates are within a fixed distance from the given point’s coordinates. For sparse data, this method of determining locality can result in some local approximations that depend on very few data points.

Renka’s modification constructs the quadratic using a fixed number of points closest to the given point. Test results in two dimensions show that this method is more accurate than the original method for a reasonable selection of test problems. Renka also describes how the searching required for these methods can be more efficiently done using Bentley and Friedman’s cell technique. The combination of these two modifications results in a faster, more accurate algorithm that extends easily to higher dimensions (some additional test results show good performance for the method in three dimensions).