假设我有一组矩形（尺寸不同或相同）。
这可以通过线性搜索/更新在 O(n) 时间内轻松解决，但是否有可能获得更好的结果？我认为 O(log n) 是最优的。插入和删除也必须比 O(n) 快，这在我的情况下才有用。
可以通过不找到最佳矩形来制作任何快捷方式，而是将第二个限制放松为：“它也应该是可以包含给定矩形的最小矩形之一” -
我正在考虑使用Z 阶曲线（宽度/高度）并将其用作一维索引并将其与树相结合。那行得通吗？还是会浪费太多？
另一种方法是使用一个轴使用树，然后线性测试另一个。
有人做过类似的事情并可以分享他们的经验吗？
这是一个尚未完全阐述的想法：
也许您可以使用具有 2 个元组值（高度和宽度）的四倍分支树，每个值代表一个矩形。
一个节点 (w, h) 有 4 个子节点：
(<w, <h)- 包含宽度和高度较小的矩形(>=w, <h)- 包含具有更大宽度和更小高度的矩形(<w, >=h)- 包含具有更小宽度和更大高度的矩形(>=w, >=h)- 包含具有更大宽度和更大高度的矩形当您在(w, h)rect 节点下降以查找 rect 的容器时，(w2, h2)现在有 4 种不同的情况：
w2<w and h2<h- 三个选项：(>=w, <h), (<w, >=h),(>=w, >=h)w2>=w and h2<h- 两个选项：(>=w, <h),(>=w, >=h)w2<w and h2>=h- 两个选项：(<w, >=h),(>=w, >=h)w2>=w and h2>=h- 一个选项：(>=w, >=h)您将不得不下降到所有可能的分支，这仍然比 O(n) 好。
插入是 O(log n)。还不确定删除和平衡。但我几乎可以肯定也有解决方案。