A similar intuition applies to the interpolation of sparse data. Given point data collected on the Earth's surface, equation (1) relates how the data is placed into the discrete computational grid. If data is collected at perfectly regular intervals on the Earth's surface, it is possible to choose a bin size such that one and only one measurement falls in each bin. On the other hand, if the data sampling is irregular, two problems may arise: 1) more than one datum may fall into a given bin, and the values averaged, implying information loss, and 2) no data may fall into a given bin, leaving a ``hole'' in the model.

Applied to interpolation, the quadtree methodology seeks to adaptively sample the model such that 1) where data are closely spaced, the bin size is small, to minimize averaging of adjacent data and 2) where data are sparsely distributed, the bin size is large, to avoid introducing holes in the model.

First assume that there exists a regular bin size such that binning the data produces a model with no holes. From here, we regard ``bin size'' as equivalent to ``scale'' - where scale goes from coarsest (largest bins) to finest (smallest bins). Also assume that at each scale, the bins which contain one or more data values are known.

- - Model at scale
*i*;*i*=0 is coarsest scale,*i*=*n*is finest scale. - - Bin data onto grid of scale
*i*;*i*=0 is coarsest scale,*i*=*n*is finest scale. - - Known data mask at scale
*i*- 1 for bins which contain data, 0 otherwise;*i*=0 is coarsest scale,*i*=*n*is finest scale. - - Upsampling operator. Upsample from scale
*i*-1 to scale*i*.*i*=0 is coarsest scale,*i*=*n*is finest scale. Adjoint to the downsampling operator in the multiscale regularization discussion. For instance, if the downsampling operator sums four input bin locations into an output location and averages, the upsampling operator takes the averaged value and places it back into the four bins. - - data.

- 1.
- Compute .
- 2.
- Loop over scale: .
- 3.
- Upsample .
- 4.
- Compute .
- 5.
- Where . Otherwise, .
- 6.
- End Loop.

9/5/2000