The LIR Space Partitioning System

We introduce a novel multi-dimensional space partitioning method. A new type of tree combines the advantages of the Octree and the KD-tree without having their disadvantages. The data structure allows local refinement, parallelization and proper restriction of transition ratios between leafs. Our technique has no dimensional restrictions at all. The tree’s data structure is defined by a topological algebra based on a ternary alphabet that encode the partitioning steps, first mentioned in [1]. The set of successors is restricted such that each cell has the partition of unity property to partition domains without overlap. With our method it is possible to construct a wide choice of spline spaces to compress or reconstruct scientific data such as pressure and velocity fields and multidimensional images. We used a generator function to build a tree that represents a voxel geometry. The space partitioning system is used as a framework to allow numerical computations. This work is triggered by the problem of representing, in a numerically appropriate way, huge threedimensional voxel geometries that could have up to billions of voxels. These large datasets occure in situations where it is needed to deal with large representative volume elements