Renka III

The Renka III algorithm is part of the Estimate Scattered Data option in the Non-Parametric menu. It is also offered in the Interpolate Uniform Grid option.

Author
Robert Renka
Dept. of Computer Sciences
University of North Texas
Denton, TX 76203-6886
E-mail: renka@cs.unt.edu
Web page: http://www.cs.unt.edu/home/renka/

References
"TSHEP2D: Cosine Series Shepard Method for Bivariate Interpolation of Scattered Data", Submitted to ACM TOMS.

Description
The Renka III procedure is a nearest neighbor weighted least-squares C2 (twice continuously differentiable) procedure that is free from the limitations of triangulation based algorithms. The nodal functions are ten parameter cosine series models whose coefficients are determined by least-squares fitting of an adjustable number of nearest neighbor data points. The algorithm also offers an adjustment of the number of nodes which define the radii of influence for the weights. Although slower than triangulation-based procedures, this algorithm was found to offer excellent accuracy with particularly difficult to model surfaces.

Revisions to Algorithm
The number of nodes which define the radii of influence for the weights is automatically set by TableCurve to a value approximately 50% greater than the local data count. The data are also intrinsically scaled to a unit square.

Interpolation
The interpolation scheme is a modified Shepard method. The interpolant is weighted sum of bivariate cosine-series nodal functions. The coefficients for each of the nodal functions are obtained by a weighted least squares fit to the closest n nearest neighbor data points. As such, the radius of influence for the least-squares fit is fixed for each node, but varies across nodes. The nearest neighbor determination is based on an efficient cell-based scheme. The radius of influence for the weights also varies with node as is needed to satisfy this second nodal count which TableCurve fixes at approximately 1.5x the count of nodes set for the least-squares fit.

Extrapolation
For a nearest neighbor procedure, extrapolation and interpolation are indistinguishable.

Estimated Partial Derivatives
All partial derivatives are computed analytically. The algorithm offers smooth and accurate first order partial derivatives.

Estimated Volumes
The primary method is to interpolate a uniform grid of 10,000 points and to evaluate the double integral using a bicubic B-spline integration procedure. The error reported in the Evaluation procedure will be the fractional difference with a similar 2,500 node integration. A repeat evaluation with the same limits will use an actual double integration procedure using the actual interpolant. A very fast double Gaussian quadrature procedure is first attempted to 1E-5 precision. If this is unsuccessful, a double adaptive quadrature procedure is then used.

Considerations
The Renka III algorithm is a well crafted nearest neighbor least-squares estimation procedure that is particularly suited difficult surfaces with periodic undulations. The procedure can vary from a global method to a very local one, depending on the nodal count used for the fitting. Accuracy tests suggested it to be a superb algorithm for particularly difficult surfaces containing multiple features.

Algorithm Adjustments
The only user adjustments for this algorithm is the count of nearest neighbor data points. The TableCurve Studio default neighbor count is 18. With this value, the node count for the radii of weighting is automatically set at 32. This number of nodes which define the radii of influence for the weights is automatically set to a value approximately 50% greater than the local data count.In the Interpolate Uniform Grid option, the nearest neighbor count is fixed at 18 or the data count, whichever is smaller.