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 N,. X N,. uniform grid of cells, and the indexes of the nodes contained in each cell are stored as a linked list in two integer arrays. Assuming a uniform distribution of nodes, the expected time complexity is О (N) for the preprocessing phase and constant for each evaluation. Worst-case operation counts are 0(N2) for preprocessing and O(N) for evaluation.
The accompanying survey article [Renka and Brown 1999] presents test results showing, that for reasonably dense data sets, CSHEP2D is among the most accurate scattered data algorithms available.
