Implementation of insert algorithm

Representation: in each node we have the relevant bounding-box and the value of function C. We also remember the path to the place where the inserted bounding-box will be added.

Algorithm for building a tree

1.

tree = one of the bounding-boxes (arbitrary)

2.

successively for all other bounding-boxes

(a)

find a place in the tree where the bounding-box should be added

(b)

add the bounding-box there

ad 2.(a) - finding a place

1.

Evaluate function C₁.

2.

If the tree is only initial bounding-box (has no successors), then there are no other possibilities. The result is C₁

3.

Evaluate function C₂.

4.

Evaluate function C₃. Try to insert into each successor and then select the variant with the lowest C (and remember the path).

5.

choose the best one from C₁,C₂,C₃ (the lowest value $\sim$ minimum number of comparisons)

ad 2.(b) - adding

According to selected variant and remembered path incorporate bounding-box into the tree. Then it is necessary to figure out new values of C on the path.

Algorithm for traversing a tree

1.

At the beginning we have to test the bounding-box in the root of the tree. If this test fails, the tested object is outside all bounding-boxes.

2.

The next steps depend on type of node:

• for internal nodes

  Test the related bounding-box in the node. If it fails then stop - there is no intersection with input bounding-boxes. Otherwise call testing recursively for each of successors.

• for leaves

  Test the bounding-box. If there is no intersection then stop. Otherwise add this bounding-box in the resultant list.

As a result we have a list of bounding-boxes intersecting or including the tested object.