高维区间树

Question

我遇到一个问题，高维区间树可能会有所帮助。我可以理解一维区间树是如何工作的。但我看不出在更高维度应该如何实现。

区间树和范围树

维基百科的解释说对每个维度使用范围树和区间树。但我看不出它是如何工作的！我不清楚那里的解释......请检查“更高维度”部分：

首先，构建一个 N 维的范围树，它可以高效检索查询区域 R 内起点和终点的所有区间。一旦找到相应的范围，剩下的就是包含该区域的那些范围某个维度。

如果范围树更高效，为什么还需要区间树？

对于“范围树”，我们可以看到它是为区间内的查询点创建的（树不存储区间）。因此，我假设维基百科的意思是：

首先，构建 N 维范围树，允许高效检索查询区域 R 内具有起点或终点的所有区间。

然后..什么？如果我从此时开始为每个维度创建一个区间树，则即使原始对象与我的查询不相交，这些区间中的任何一个都将位于我的搜索框上。请检查下面的图片，尝试形象化我所说的内容。

也许，我不清楚的是：如何交叉两个区间树的区间结果以确保它位于一个实体上？

有人可以解释一下在这种情况下如何使用范围树吗？

R树

---

顺便提一下，我知道 R Tree 的存在。但我想先了解高维的区间树。此外，正如注释一样，在维基百科

他们说：

区间树 – 一维（通常是时间）的退化 R 树。

我强烈不同意。否则，为什么我们应该谈论高维区间树？如果我很好地理解这两种方法：

R Tree 使用 MBR 对实体进行分组，而 Interval Tree 使用点。

R Tree 可以存储任何类型的空间实体，而 Interval Tree 只存储间隔。

R Tree 需要时不时地分裂节点，这似乎很昂贵。区间树永远不会分裂节点。

范围树用于获取具有查询超立方体内顶点的轴对齐超立方体 - 所有这些超立方体都与查询超立方体相交。

Answer 1

使用单维区间树（在每个轴上）（我猜？）来寻找完全覆盖（沿着某个轴）查询超立方体的超立方体——我假设每个轴都被咨询，然后结果相交找到这套。