Quad- and octtrees for two and three dimensions, respectively, have been successfully applied to the LS method [46,71,81,121]. The LS values of defined grid points are stored within leaf nodes and can be accessed in logarithmic time. By using an adaptive grid with increasing resolution close to the surface, an optimal linear scaling law with surface area can be obtained. At the surface the same maximum resolution is generally used, because the solution of the LS equation with the finite difference method is more complex and less accurate on non-uniform grids.
Despite the optimal scaling law, the internal pointer structure of trees leads to a significant memory overhead. Furthermore, the memory layout of trees is usually not very convenient for fast serial processing.