Complexity

Let's expect specification:

• n ... number of initial bounding-boxes
• q ... number of tested objects (q >> n)
• complexity of test of intersection between tested object and bounding-box = O(1)

Now we can look at particular methods for solution:

successively

• time complexity: $O(q\cdot n\cdot 1)=\underline{O(q\cdot n)}$
• memory complexity: $\underline{O(1)}$

binary tree

• building a tree

  1.

  figure out values for all pairs of bounding-boxes $\Rightarrow O(n^2)$

  2.

  sort these values $\Rightarrow O(n^2\cdot \log n)$

  3.

  in each step group two bounding-boxes together: $O(n) \times$

  (a)

  select maximum value - two selected bounding-boxes $\Rightarrow O(1)$

  (b)

  remove all combinations with two selected bounding-boxes $\Rightarrow O(n)$

  (c)

  inserting combinations with new bounding-box $\Rightarrow O(n\cdot \log n)$

  4.

  all together: $O(n^2\cdot \log n)$

• time complexity: the best $\underline{O(q\cdot \log n)}$, the worse $\underline{O(q\cdot n)}$

  1.

  building a tree: $O(n^2\cdot \log n)$

  2.

  searching: the best $O(q\cdot \log n)$, the worse $O(q\cdot n)$ (distribution of tree, overlapping bounding-boxes)

  3.

  be aware of condition: $O(q\cdot \log n) >> O(n^2\cdot \log n)$, otherwise it is not efficient (better than successively)

• memory complexity: $\underline{O(n)}$ - tree

• disadvantage:

  1.

  If there are many overlapping bounding-boxes, we have to traverse larger parts of the tree.

insert algorithm

• building a tree: We incorporate n bounding-boxes one by one into the tree. The tree has O(n) nodes, which we have to pass every time. Modification of the tree has complexity $O(\log n)$. All together it is $O(n\cdot (n+\log n))=\underline{O(n^2)}$

• time complexity: the best $\underline{O(q\cdot \log n)}$, the worse $\underline{O(q\cdot n)}$

  1.

  building a tree: O(n²)

  2.

  searching: the best $O(q\cdot \log n)$, the worse $O(q\cdot n)$

  3.

  the important condition: $O(q\cdot \log n) >> O(n^2)$

• memory complexity $\underline{O(n)}$ - tree

example of one another approach - only for comparison

Top-down method, dividing space by projection of bounding-boxes in axes.

• time complexity: $\underline{O(q\cdot \log n)}$ always
• memory complexity: $\underline{O(n^2)}$
• advantages: unambiguous in searching, faster, better for very overlapping bounding-boxes
• disadvantage: bigger consumption of memory