Note that it is not necessary to compute the associated cell B(ν) each time. The current

cell is maintained through the recursive calls using only the information on the splitting

value s(ν) and the splitting dimension d(ν). For example, the cell for the left child ν1 of a

node ν is

B(ν1 ) = B(ν) © {x ∈ Rd : xd(ν) ¤ s(ν)}.

The complexity analysis of the range query shows that Algorithm 5 needs slightly more

time to answer a range query problem than Algorithm 2, if the data points are quasi-uniform

and if the range has size O(h). This is a natural consequence of the tree structure.

Proposition 14.7 Let X = {x1 , . . . , x N } ⊆ Rd be quasi-uniform in its bounding box B B.

Suppose that the query region R is of size O(N ’1/d ). If its bounding box can be computed

in constant time and if it is also possible to decide in constant time whether a point belongs

to R, then Algorithm 5 needs O(log N ) time to report all points contained in R.

Proof If X is quasi-uniform in its bounding box then each splitting rule divides the current

box into two boxes that have a side length in the direction of the spitting dimension that

is roughly half the side length of the original box. Hence no coordinate is preferred by the

splitting rule and the boxes associated with the leaves have side lengths O(h X,B B ) in each

coordinate. Since the query region has also size O(h X,B B ), only a constant number of leaf

boxes has to be investigated. Finally, since the depth of the tree is O(log N ), the complexity

for reporting all points contained in R is O(log N ).

Next, let us have a look at the nearest-neighbor problem. There are different ways of

implementing a strategy for this problem using a kd-data structure. The standard procedure

is given in Algorithm 6.

Algorithm 6 Nearest neighbor search

Query point x and root ν of kd-tree.

Input:

Output: A point x j ∈ X that is closest to x.

Initialize the distance dist as in¬nity and reserve space to store the nearest neighbor nn.

if ν is a leaf then

Compute the distance of each point stored in ν to x.

if the current distance is less than dist then

Update dist and nn.

if ν is a splitting node then

Visit that child of ν whose associated box contains x.

The other child has only to be visited if its associated box has a distance to x that is less

than the current distance dist.

Return nn.

242 Data structures

The generalization to the nearest neighbors problem is obvious again. The same is

true for the analysis in the case of quasi-uniform points. In view of the facts that each

box associated with a leaf has size O(h) and that two parallel splitting hyperplanes have

separation distance at least O(h), only a constant number of leaves will be visited. Since

the tree has depth O(log N ), we can make the following proposition:

Proposition 14.8 Let X = {x1 , . . . , x N } ⊆ Rd be quasi-uniform in its bounding box B B.

For every x ∈ Rd , Algorithm 6 needs O(logN ) time to ¬nd the nearest neighbor of x.

Since our result on building the kd-tree does not depend on quasi-uniformity it is inter-

esting to see how our algorithms behave if X is not quasi-uniform. There is a very large

number of results addressing this problem. Here, we want to give only one of them. To this

end we assume that the kd-tree has been built using the cyclic splitting rule.

Proposition 14.9 A range query with an axis-parallel rectangle R can be performed in

O(N 1’1/d + k) time, where N is the number of points in the kd-tree and k is the number of

reported points.

Proof Since each point contained in the query region is dealt with exactly once in a “report

all points” call of Algorithm 5, the time necessary to report all relevant points is linear in

the number k of reported points.

Hence, it remains to estimate the time spent in nodes that are not traversed by “report all

points” calls. To this end we investigate the number of associated boxes that are intersected

by a hyperplane orthogonal to the ¬rst coordinate. This gives an upper bound on the boxes

intersected by the two side faces of the query box that are orthogonal to the ¬rst coordinate.

The number of regions intersected by the other faces can be bounded in the same way. Let

Q(N ) denote the number of intersected regions in a kd-tree with N points, whose root has

splitting dimension 1. Let H be the hyperplane orthogonal to the ¬rst coordinate in question.

Since the root has splitting dimension 1, H intersects one of its two children but not both.

However, it intersects both children of this child because both have splitting dimension 2.

Continuing this argument we arrive after d splitting steps at nodes that again have splitting

dimension 1. Hence, the recursion for Q(N ) is given by

Q(N ) = 2d’1 + 2d’1 Q(N /2d ),

because in each splitting step the number of points in the new boxes is reduced by a factor

2. As Q(1) = O(1) this recursion solves to give Q(N ) = O(N 1’1/d ).

In most numerical examples the range query behaves much better than is predicted by

the last proposition. Nonetheless, an improvement can be achieved, at least theoretically,

by using the following bd-trees.

If working with cyclic splitting then it is sometimes favorable to subsume one complete

cycle into one node. This means that in each step the associated box is divided into 2d

subboxes and that each node has 2d children. Special cases of the resulting trees are quadtrees

in a two-dimensional setting and octrees in a three-dimensional setting.

14.3 bd-Trees 243

Finally, kd-trees can also be used to construct an overlapping domain decomposition,

which is useful for a containment query. The only thing that has to be changed is that instead

of one cutting hyperplane there now have to be two. All points on the left of the right cutting

plane are assigned to the left child and all points on the right of the left cutting plane to the

right child.

14.3 bd-Trees

While kd-trees work ef¬ciently in moderate space dimensions and if the data points do not

deviate too much from quasi-uniformity, something more elaborate has to be done in other

cases. In particular, when the points are highly clustered, either it may take many splits to

partition them or the splits may result in arbitrary long boxes, which might cause problems

when searching is performed.

One possible way of avoiding such problems is to use bd-trees. The name stands for box

decomposition trees.

A bd-tree is a generalization of a kd-tree. It is still a binary tree but in addition to leaves

and splitting nodes a third type of node is introduced. The new type of node represents an

additional operation called shrinking. Consider a node whose associated box B contains

more points than the bucket size. Then, a shrinking rule is invoked. This rule may either

perform a split according to the chosen splitting rule or select an axis-parallel box B1

contained inside B. The points lying in B1 are assigned to one child and the points lying

in B2 = B \ B1 are assigned to the other child. Points on the boundary may be assigned to

one or both children. We will describe possible shrinking rules by employing the notation

already used in the kd-trees setting.

r No shrink Do not perform any shrinking at all, only splitting.

r Simple shrink This rule depends on two constants: tn (for example this could equal 2) and thresh

(for example this could equal 0.5). It ¬rst computes the 2d distances between each side of the

bounding box B(Y ) of the current data set Y and the corresponding side of the box B associated

with the current node. If at least tn of these distances are larger than the length of the longest side of

B(Y ) times thresh then it shrinks all affected sides. After the shrink, Y is completely contained in

the inner box while the outer box contains no point at all. If the criterion is not met then a classical

split is performed.

r Centroid shrink This rule also depends on two constants: ms (for example 4) and f r

(for example 0.5). Theoretically speaking, it applies the splitting rule, without actually gener-

ating a splitting node, to ¬nd the half space that contains the larger number of points, and it goes

on splitting this part until the actual number of points is less than f r times the initial number. If

more than ms splits are necessary then a shrinking node corresponding to the ¬nal inner box is

created; all other points are placed in the outer box. Otherwise, splitting is performed.

While the “no shrink” choice leads to a kd-tree, the other shrinking rules may lead to a

different decomposition of space. Figure 14.5 shows the data points of Figure 4.4 but now

for a bd-tree with simple shrink and sliding midpoint split. The centroid shrink would lead

here to the same decomposition as the splitting rule alone.

244 Data structures

Fig. 14.5 A bd-tree decomposition with simple shrinking rule.

Building a bd-tree structure is very similar to building a kd-tree structure. The necessary

modi¬cations of Algorithm 4 should cause no problem. Hence we leave the details to the

reader.

We will still call the outer box a box, even if it is not a box in the literal sense any more.

The concerned reader might replace the word box by “cell” and de¬ne a cell to be either a

box or the set-theoretical difference of two boxes.

Note that every splitting operation can be seen as a special case of a shrinking operation,

with the inner box as (for example) the left-hand box and the outer box as the original box.

But this is not optimal because it needs more comparisons to decide whether a point is in a

box than to decide on which side of a hyperplane it is situated.

Range queries and a nearest neighbor search can be performed in just the same way as