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!
$\begingroup$
$\endgroup$
2
-
$\begingroup$ Have you tried adapting quad-trees? Seems to me that such a modification should not influence the basic operations and their cost much. $\endgroup$– RaphaelCommented Apr 1, 2017 at 12:43
-
$\begingroup$ That's exactly what I'm going to do! I'm just frustrated because I can't think of a name for my new Tree class and it feels like such a structure must already have a name! $\endgroup$– James BedfordCommented Apr 1, 2017 at 13:29
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
1
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.
-
$\begingroup$ A bounding interval hierarchy is a related data structure that may also be worth looking into. $\endgroup$ Commented Apr 2, 2017 at 5:18
$\begingroup$
$\endgroup$
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.
