Next: Solution
Up: No Title
Previous: Introduction
We presuppose two-dimensional Euclid's space and Cartesian
rectangular system of co-ordinates. Than we have chosen the following
constraints:
- bounding boxes are rectangles parallel to co-ordinate axes
- a hierarchy is represented by a general tree (not restricted to binary)
- bounding-boxes can overlap themselves
- a number of tested objects is much bigger than a number of bounding boxes
- the distribution of probability for location of tested object is constant
in the whole space, it means that it has no relation to the distribution of
bounding boxes
Time complexity should be better than O(n), it means better than
processing bounding-boxes one by one.
There are several methods how can be this problem solved, we have chosen
only one for this text, which is based on inserting bounding-boxes into
the tree one by one.
It is necessary to point out, that building a tree takes a lots of time.
For overall efficiency is advantageous to traverse the tree many times.
1999-04-11