Quadtree Matrices

Matrices

I'm going to assume that you know what a matrix is. (Insert stupid "not a virtual reality created by robot overlords" and "not a Gallifreyan computer for Time Lord memories" jokes here.) If you need a refresher, look up matrix at Wikipedia.

The important thing to know for this recess break is that matrices are a grid of numbers (or other algebraic entities like polynomials).

Quadtrees

The Wikipedia article on quadtrees focuses mostly on geometry applications. The data structure is the same as for matrices, it's just a matter of what's stored at the leaves.

Quadtree Matrices

Quadtree matrices are recursive. The simple base case is that a single number, a scalar, is a quadtree matrix, a leaf node.

The general, recursive case is to take a general matrix, and split it into quadrants: split the matrix in half horizontally and vertically. Consider this example from my dissertation:

Look how the quadrant in the upper left, what we call the northwest quadrant, is found as the first subtree of the quadtree. The northwest quadrant of that quadrant (the 2.1) is the first subsubtree of the subtree. Similarly, the northeast quadrant is second, followed by the southwest and southeast.

This example also demonstrates what we do with matrices that aren't easily chopped in half all the way down. We'd like every matrix to have an order which is a power of 2, but that's just not going to happen. Instead, we pad out each matrix with zeros on the east and south to get the order to a power of 2. In the example above, it means only adding one column and one row of zeros, but in general many columns and rows of zeros may be added. But notice in this example that the 0.0 scalars in the original matrix are turned into special leaf nodes, labeled "Z" for "zero", of course. While all scalars will appear on the same level of the quadtree matrix, a zero leaf can appear anywhere (as another base case), and the space we use is only a log (base 2) compared to storing all of the raw 0.0s.

Haskell Code

We represent a quadtree matrix in Haskell as an algebraic type.

data Matrix a = ZeroM | ScalarM a |
  QuadM (Matrix a, Matrix a, Matrix a, Matrix a)
    deriving (Show, Eq)

As described above, a quadtree matrix is either a zero matrix, a scalar matrix, or a quadtree node of four quadtree matrices.