An efficient representation of quadtrees and bintrees for multiresolution terrain models

A space-filling curve in 2, 3, or higher dimensions can be thought as a path of a continuously moving point. As its main goal is to preserve spatial proximity, this type of curves has been widely used in the design and implementation of spatial data structures and nearest neighbor-finding techniques. This paper is essentially focused on the efficient representation of Digital Elevation Models (DEM) that entirely fit into the main memory. We propose a new hierarchical quadtree-like data structure to be built over domains of unrestricted size, and a representation of a quadtree and a binary triangles tree by means of the Hilbert and the Sierpinski space-filling curves, respectively, taking into account the hierarchical nature and the clustering properties of this kind of curves. Some triangulation schemes are described for the space-filling-curves-based approaches to efficiently visualize multiresolution surfaces.