The H-RLE data structure does not support efficient insertion or deletion of defined grid points except at the end. However, the sparse field LS method changes the set of defined grid points at every time step. The only efficient way to get a new H-RLE data structure with a different set of defined grid points is to set it up from the beginning. This can be carried out on-the-fly by simultaneously iterating over the existing H-RLE data structure and inserting the desired defined grid points into the new data structure.

In the following sections the realization of the sparse field LS method for the H-RLE data structure is described in further detail. Every time step requires the application of a couple of operations which all process the H-RLE data structure sequentially using the previously described iterators. As a consequence, all these operations exhibit a linear performance.

The sparse field implementation extends the original H-RLE data structure by one additional array which has the same size as the array holding the LS values. For each defined grid point an integral value is stored, which gives information on whether a defined grid point is active or not. In the first case, the corresponding value gives the number of the active grid point. The numbering corresponds to the lexicographical order of active grid points. By contrast, non-active defined grid points are indicated by setting the corresponding array entries to the maximum representable value.

Otmar Ertl: Numerical Methods for Topography Simulation