where dik is the distance between nodes i and k, and Rc is a radius of influence about node k; Ck depends only on the data values at nodes within distance Rc of (xk, yk). The weight u>kk associated with node k is taken to be a large value so that Ck interpolates fk at node k.
The radii Rc and Rw vary with k and are taken to be just large enough to include Nc and Nw nodes, respectively, for fixed values of Nc and Nw. The optimal values of these parameters depend on the data set, but accuracy varies smoothly and gradually with variations in the values. The default recommendations, found to be optimal for a set of test cases, are Nc = 18 and Nw = 32. Slightly smaller values may produce better results on sparse data sets.
Note that, in general, the support of С is the union of a set of node-centered disks with radii that depend on Nw. If the nodal density varies widely, this union of disks may not cover the convex hull of the nodes, i.e., the convex hull could include points (x, y) for which C(x, у) = О because (x, y) is not within the radius of influence of any node. Thus, it may be necessary to use a larger value of Nw in order to avoid this situation.
The cell-based search method is used in the preprocessing phase to determine an ordered sequence of nearest neighbors to each node, and in the evaluation phase to find the set of all nodes whose radii Rw include the evaluation point. The smallest rectangle containing the nodes is partitioned into an Nr X Nr uniform grid of cells, and the indexes of the nodes contained in each cell are stored as a linked list in two integer arrays. For maximum efficiency, the recommended value of Nr is ^N/3. Assuming a uniform distribution of nodes, the expected time complexity is O(N) for the preprocessing phase and constant for each evaluation. Worst-case operation counts are 0(N2) for preprocessing and 0(N) for evaluation.
The accompanying survey article [Renka and Brown 1999] presents test results showing that, for difficult test funtions, TSHEP2D is among the most accurate scattered data algorithms available.
2. CODE
The software is written in 1977 ANSI Standard Fortran and uses double precision. It can be converted to single precision by simply replacing all occurrences of'double precision' or 'dble' by 'real'. Note, however, that there is a significant amount of roundoff error, particularly in evaluating partial derivatives, and IEEE standard single precision is not sufficient. There are no system dependencies. The array storage requirements consist of three order-ЛГ arrays, x, Y, f, containing the data points, a 10 X N array
ACM Transactions on Mathematical Software, Vol. 25, No. 1, March 1999.
