Akima I

The Akima I algorithm is part of the Estimate Scattered Data option in the Non-Parametric menu. It is also offered in the Interpolate Uniform Grid option. Note that the Akima II procedure overcomes many of the limitations of this earlier algorithm.

Author
Hiroshi Akima

References
"A Method of Bivariate Interpolation and Smooth Surface Fitting for Irregularly Distributed Data Points", ACM Transactions on Mathematical Software, Vol. 4, 1978, p144-159, Also "Algorithm 526", p160-164.

Description
For the Akima I algorithm, the late Hiroshi Akima’s ACM 526 procedure is implemented. This algorithm is perhaps the best known of triangulation-based surface fitting algorithms and was one of the first to be placed in the public domain.The algorithm uses a Delaunay triangulation and local gradients computed using a number of neighboring points, which is locked at 5 in TableCurve Studio. The additional points used for the gradient estimation aid in preserving global shape properties. The interpolant for each triangle is a 21 coefficient C1 (once continuously differentiable) Hermite bivariate quintic polynomial. This algorithm also offers a very stable form of extrapolation.

Revisions to Algorithm
An improvement for the computation of the coefficients of the interpolant was implemented (Preusser, A., "Remark on Algorithm 526", ACM Transactions on Mathematical Software, Vol. 11, No. 2, p186-7, June 1985). The data are also intrinsically scaled to a unit square. Routines were also added which compute exact analytic partial derivatives. A suggestion by Albrecht Preusser has also been implemented which prevents the selection of close to collinear points for the partial derivative computations. This modification also manages most instances of collinearity of non-axially aligned neighbor points.

Interpolation
This algorithm is based upon quintic Hermite polynomials on triangles. There is one polynomial for each triangle, whose coefficients are determined by the partial derivatives at the nodes of the triangle mesh. Five partial derivatives are computed at each node within the convex hull boundary of the data. The interpolant consists of 21 coefficients for every triangle, 18 values at the nodes with 3 additional conditions that assure continuity of first partial derivatives across triangle edges. With 5 partial derivatives per node, 15 total partial derivatives are used per triangle. In the gradient computations, neighboring points are determined based on actual distances from the target point. Due to the revisions which implement unit normalization of the x and y scales and where neighbors are regarded as collinear within a 15 degree band between the point and nearest neighbor, the points used for the gradient computations will usually result in a stable interpolant, regardless of the x and y scaling and data density.

Extrapolation
The algorithm directly provides for extrapolation and maintains a C1 boundary at the transition to the extrapolation regions. The algorithm uses two different lower coefficient count extrapolants to produce stable extrapolations. For extrapolations, only the first two partial derivatives are used at the boundary nodes.

Estimated Partial Derivatives
Full analytic derivatives are available (once with respect to x, to y, twice with respect to x, to y, and with respect to both x and y). These are used for graphing the partial derivative surfaces and for partial derivatives computed in the Evaluation procedure. The first order partials will be continuous, but not smooth. The higher order partials will not be continuous.

Estimated Volumes
The 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. Because the Akima I algorithm is extremely inefficient with individual function evaluations, the alternative integration procedures available with the other algorithms are not offered here. Repeat evaluations with the same integration limits serve no purpose with the Akima I procedure.

Quick Evaluations
The Akima I procedure is exceedingly inefficient when individual evaluations must be made. As such, a considerable length of time will be required for the update of the quick evaluation feature if the surface minimum or maximum is being sought (a large number of individual interpolations may be needed in the two dimensional minimization).

Considerations
The local nature of the gradient computations is subject to undue influence from the distant nodes that occurs within thin triangles. Further, since a Delaunay triangulation is often not unique, an anomalous point can have a variable influence in the estimated surface depending on the order of the input data. A global gradient estimation procedure can somewhat alleviate this effect. An Akima-type quintic interpolant which uses such a procedure is available with the C1 form of the Preusser option. One advantage of the Akima approach for gradient estimations is that the effects of local features that genuinely belong in the data can be generally restricted to a minimal effect on adjacent regions of the surface. In general, the Akima I algorithm is likely to be the amongst the least accurate of the scattered data procedures. Accuracy tests confirmed the newer Akima II procedure to be considerably more accurate.

Algorithm Adjustments
Akima recommended a value of 3-5 (inclusive) additional points for this algorithm. The TableCurve Studio fixed value of 5 was empirically found to be an effective value for properly handling single node peaks and valleys.

IMSL Implementation
The IMSL version of this algorithm (SURF) is offered as a separate item in the Interpolate Uniform Grid option. It is included because of its general use as a means for creating a grid from scattered data, and since it uses a proprietary method for gradient computation. Unit square scaling is implemented. Since the IMSL version functions only as a gridding procedure, it is not included in the Estimate Scattered Data option.