next up previous
Next: Complexity Up: Solution Previous: Inserting

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 C1.
2.
If the tree is only initial bounding-box (has no successors), then there are no other possibilities. The result is C1
3.
Evaluate function C2.
4.
Evaluate function C3. 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 C1,C2,C3 (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.


next up previous
Next: Complexity Up: Solution Previous: Inserting

1999-04-11