Implicit k-d tree

Splitting-functions may be adapted to special purposes. Underneath two specifications of special splitting-function classes.

• Non-degenerated splitting-functions do not allow the creation of degenerated nodes (nodes whose corresponding integer hyperrectangle's volume is equal zero). Their corresponding implicit k-d trees are full binary trees, which have for n leaf nodes n - 1 inner nodes. Their corresponding implicit k-d trees are non-degenerated implicit k-d trees.
• complete splitting-functions are non-degenerated splitting-functions whose corresponding implicit k-d tree's leaf nodes are single grid cells such that they have one inner node less than the amount of gridcells given in the grid. The corresponding implicit k-d trees are complete implicit k-d trees.

A complete splitting function is for example the grid median splitting-function. It creates fairly balanced implicit k-d trees by using k-dimensional integer hyperrectangles hyprec[2][k] belonging to each node of the implicit k-d tree. The hyperrectangles define which gridcells of the rectilinear grid belong to their corresponding node. If the volume of this hyperrectangle equals one, the corresponding node is a single grid cell and is therefore not further subdivided and marked as leaf node. Otherwise the hyperrectangle's longest extent is chosen as orientation o. The corresponding split plane p is positioned onto the grid plane that is closest to the hyperrectangle's grid median along that orientation.

Split plane orientation o:

o = min{argmax(i = 1 ... k: (hyprec[1][i] - hyprec[0][i]))}

Split plane position p:

p = roundDown((hyprec[0][o] + hyprec[1][o]) / 2)

An advantage of implicit k-d trees is that their split plane's orientations and positions need not to be stored explicitly.

But some applications require besides the split plane's orientations and positions further attributes at the inner tree nodes. These attributes may be for example single bits or single scalar values, defining if the subgrids belonging to the nodes are of interest or not. For complete implicit k-d trees it is possible to pre-allocate a correctly sized array of attributes and to assign each inner node of the tree to a unique element in that allocated array.

The amount of gridcells in the grid is equal the volume of the integer hyperrectangle belonging to the grid. As a complete implicit k-d tree has one inner node less than grid cells, it is known in advance how many attributes need to be stored. The relation "Volume of integer hyperrectangle to inner nodes" defines together with the complete splitting-function a recursive formula assigning to each split plane a unique element in the allocated array. The corresponding algorithm is given in C-pseudo code underneath.

// Assigning attributes to inner nodes of a complete implicit k-d tree

// create an integer help hyperrectangle hyprec (its volume vol(hyprec) is equal the amount of leaves)
int hyprec[2][k] = { { 0, ..., 0 }, { length_1, ..., length_k } };
// allocate once the array of attributes for the entire implicit k-d tree
attr *a = new attr[volume(hyprec) - 1];

attr implicitKdTreeAttributes(int hyprec[2][k], attr *a)
{
  if (vol(hyprec) > 1) // the current node is an inner node
  {
    // evaluate the split plane's orientation o and its position p using the underlying complete split-function
    int o, p;
    completeSplittingFunction(hyprec, &o, &p);
    // evaluate the children's integer hyperrectangles hyprec_l and hyprec_r 
    int hyprec_l[2][k], hyprec_r[2][k];
    hyprec_l       = hyprec;
    hyprec_l[1][o] = p;
    hyprec_r       = hyprec;
    hyprec_r[0][o] = p;
    // evaluate the children's memory location a_l and a_r 
    attr* a_l = a + 1;
    attr* a_r = a + vol(hyprec_l);
    // evaluate recursively the children's attributes c_l and c_r 
    attr c_l = implicitKdTreeAttributes(hyprec_l, a_l);
    attr c_r = implicitKdTreeAttributes(hyprec_r, a_r);
    // merge the children's attributes to the current attribute c 
    attr c = merge(c_l, c_r);
    // store the current attribute and return it
    a[0] = c;
    return c;
  }
  // The current node is a leaf node. Return the attribute belonging to the corresponding gridcell
  return attribute(hyprec);
}

It is worth mentioning that this algorithm works for all rectilinear grids. The corresponding integer hyperrectangle does not necessarily have to have sidelengths that are powers of two.