使用RTrees搜索网格之间的交集的复杂性

Question

我有两个网格(来自有限元，但这并不相关(，比如T_1，T_2。一个网格在另一个网格内，例如，想象一个正方形在另一个中。对于每个网格，我构建了一个RTree，其中包含boost个边界框，比如RTree1和RTree2。为了找到所有相交的矩形对，我执行以下

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);
}
}
}

假设第一棵树有N边界框，第二棵树有M边界框。我想确定上面片段的复杂性。由于交集的复杂度为O(log(N))(平均值(，我认为上面的片段的复杂度是O(N M log(N))。这是正确的吗？

---

如果上面的代码是这样写的：

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));
}
}
}

我应该有一个O(NM log(N))，对吧？

Answer 1

由于交集的复杂性为O(log(N((

你在这里说什么十字路口？如果您谈论的是整个query(由于包含了N，这似乎最有意义(，那么您不应该在查询之外再次乘以N。因此，我认为是O(M log(N)。