Complexity of searching for intersection between grids with RTrees

bobinthebox 0
Viewed 34

I have two grids (coming from finite elements, but this is not relevant), say T_1, T_2. One grid is inside the other, think of a square inside another one for instance. For each grid I have constructed an RTree with boost of bounding boxes, say RTree1 and RTree2. To find all the pair of intersecting rectangles, I do the following

for (const auto &[box2, cell2] : RTree_2)
      {
        for (const auto &[box1, cell1] :
             RTree1 | bgi::adaptors::queried(bgi::intersects(box2)))
          {
             do_something_with_cells(cell1,cell2);

          }
      }
  }

Let's say that I have N bounding boxes for the first tree and M bounding boxes for the second tree. I want to determine the complexity of the snippet above. Since the intersection has a complexity which is O(log(N)) (on average), I think the snippet above has a complexity which is O(N M log(N)). Is this correct?

If the code above was written like this:

for (const auto &[box2, cell2] : RTree_2)
      {
        for (const auto &[box1, cell1] :
             RTree1)
          {
             //check if box1 and box2 intersects using bgi
             bgi::query(box1,bgi::intersects(box2));
          }
      }
  }

I should have a O(NM log(N)), right?

boost space-complexity intersection tree performance
1 Answers

Since the intersection has a complexity which is O(log(N))

What intersection are you talking about here? If you're talking about the entirety of the query (which seems to make most sense due to your inclusion of N), then you should not have to multiply N again outside the query. I think it is O(M log(N) therefore.

sehe0
Related