I'm looking for a data structure that is like a quadtree where each level is a subdivision of the previous. However, unlike a quadtree I need the subdivision to occur a different number of times in the horizontal direction to the vertical direction. In a quadtree the space is subdivided once in each dimension (resulting in four children per node). In the tree I'm looking for the space may be divided a given number of times in one dimension and a different number of times in the other. Say for example, twice in the X and once in the Y (resulting in six children per node). Has such a space partitioning tree been given a name? Can anyone point me to an existing data structure that fulfills this requirement? Thanks!
You could use a k-d tree. A k-d tree normally alternates between partitioning horizontally and partitioning vertically, but you could certainly modify it to change that pattern (e.g., partition horizontally twice in a row; or equivalently, partition horizontally into three or four regions rather than just into two regions).
Not everything has a "name". There are many more possible algorithms and data structures than there are "names". So don't take it as some kind of negative if you can't find a "name" for it. "Modified quadtree" or "modified k-d tree" will do fine, if you need a way to refer to it.
Have you looked at STR-tree (sort-tile-recursive loaded R-Trees)? See examples here and here. The basis is an R-tree. The STR-algorithm load it in a way that resembles a grid. For example in 2D space, when you specify a node size of 25, it will try to divide the space into a recursive tree of 5x5 nodes. That means each node will contain a 5x5 grid of subnode, except for the leaf nodes, which will contain 25 data points/rectangles. Note that the splitting is usually not a regular grid of squares (covering the same amount of space), instead it creates rectangulars such they each cover the same amount of data points. I'm sure this loading algorithm could be modified to form other types of grids, such as 3x8, if you wish.
This algorithm is meant for initial bulk-loading of data. Once the loading is done, additional insertions (or removals) may destroy the grid-like pattern.