Inserting

We take one of initial bounding-boxes as a base of the future tree, doesn't matter which one. Then the other bounding-boxes are put into the tree one by one (in no particular order).

(Note: In fact the difference between the tree that we will get and the ideal tree depends just on the order and the selection of the first one, but we didn't solve this problem.)

Let's have a tree of bounding boxes and one bounding-box (B) that we want to insert into the tree. (Starting with the root A). See the Fig. 2.

 

Figure 2: Inserting bounding-box in the tree

Than we have three possibilities how to do it:

1.

Create new bounding box over A and B. See Fig. 3(a).

 

Figure 3: Inserting bounding-box at the same level as original root (a) and as one of successors (b)

2.

Put B as one of the successors of A. See Fig. 3(b).

3.

Insert bounding-box B somewhere inside one of the successors A_i.

Now we will express the function C (which means number of comparisons) for each of the situations above.

1.

Inserted bounding-box at the same level as original root. C(B)=0 because B is a leaf.

$$2+{S(A-B)\over S(S)}\cdot C(A)+{S(B-A)\over S(S)}\cdot C(B)+ {S(A\cap B)\over S(S)}\cdot (C(A)+C(B))$$ C₁(S) =

$$2+{S(A-B)\over S(S)}\cdot C(A)+{S(B-A)\over S(S)}\cdot 0+ {S(A\cap B)\over S(S)}\cdot (C(A)+0)$$ C₁(S) =

$$\underline{2+{S(A)\over S(S)}\cdot C(A)}$$ C₁(S) =

2.

Inserted bounding-box as one of successors.

$$(n+1)+\sum_{i=1}^{n}{S(A_i)\over S(A')}\cdot C(A_i)+{S(B)\over S(A')} \cdot C(B)$$ C₂(A') =

$$(n+1)+\sum_{i=1}^{n}{S(A_i)\over S(A')}\cdot C(A_i)$$ C₂(A') =

now substitute from relation for the original root:

$$n+\sum_{i=1}^{n}{S(A_i)\over S(A)}\cdot C(A_i)$$ C(A) =

$$\sum_{i=1}^{n}{S(A_i)\over S(A)}\cdot C(A_i)$$ = C(A)-n

then we get:

$$(n+1)+{1\over S(A')}\cdot (C(A)-n)\cdot S(A)$$ C₂(A') =

$$\underline{(n+1)+{S(A)\over S(A')}\cdot (C(A)-n)}$$ C₂(A') =

3.

Insert bounding-box B somewhere inside one of the successors A_i.

This means complete recursion. It seems like a big disadvantage that we have to parse the whole tree every time, but as the tree has complexity only O(n), it is not so significant.

The result from this situation is a value C₃(A'), which is the lowest from all possible values for placing B inside A₁ or A₂,...,A_n.

In the end we'll choose that variant, which has the lowest value of C, it means the minimum number of comparisons.