Cyclic interlaced quadtree algorithms for quincunx multiresolution

Recent advances in wavelet theory and in finite element computations draw attention to a well-known, simple, and computationally efficient triangulation method. We take a new look at this triangulation, which is obtained by repeated symmetric bisection, starting with a half square. The cells form the leaves of a binary tree and the nodes of a directed graph consisting of a single simple cycle. Computational speed is facilitated by the binary and quad-digit expression of triangle vertices, which reduce all vertex calculations to simple integer and logical operations. The leaf cycle interlaces a pair of quadtrees whose orientations differ by pi/4. Detailed analysis leads to algorithms which exploit the structure and computational efficiencies in calculations such as pyramid algorithms for image processing with non-separable wavelets. (C) 1998 Academic Press.