Building a hierarchy

The question is how to find the structure of a tree in order that the number of comparisons will be minimal (i.e. how to minimize the function C(B)). There are two basic approaches:

1.

bottom-up method, in each step we find two "closest" bounding-boxes, group them together and continue with new one instead of them. There are many variants of what we can choose as relation "closest" e.g.:

• the shortest distance between given bounding-boxes
• the smallest area of resultant bounding-box
• the biggest ratio of the area of resultant bounding-box and the area of the union of given bounding-boxes
• combination of previous

2.

insert algorithm - consequent adding bounding-boxes one by one into the tree

Generally there is a disadvantage of both approaches: if there are many overlaps among initial bounding-boxes the tree structure will be not efficient.

We have chosen the second approach - the insert algorithm, because it solves at least partially the problem of many overlapping bounding-boxes. It allows to create trees with more than two successors in one node. This can't be done easily by the first approach, because the number of combination is too large.

The basic idea of the insert-algorithm is to place a given bounding-box locally into the tree but not to modify the tree structure in a global way. The complex modifications would be necessary when building an optimal tree structure. But for our data is suboptimum solution good enough. See section 5 for details.