找出能容纳另一个矩形的面积最小的矩形
Find the rectangle with the smallest area that can hold another rectangle
假设我有一组矩形（尺寸不同或相同）。
- 任务是从集合中找到（并移除）大于或等于给定矩形的矩形。
- 它也应该是集合中可以包含给定矩形的最小矩形。
这很容易通过线性搜索/更新在 O(n) 时间内解决，但是否有可能获得更好的结果？
我认为 O(log n) 是最优的。
插入和删除也必须比 O(n) 快，因为这对我的情况有用。
是否可以通过不寻找最佳矩形来创建任何捷径，而是将第二个限制放宽为：
"It should also be one of the smallest rectangles that can encompass the given rectangle"-
我正在考虑使用 Z-order curve（属于 width/height）并将其用作一维索引并将其与树结合。
那行得通吗？还是会浪费太多？
另一种方法是使用一个轴使用树，然后线性测试另一个。
有没有人做过类似的事情，可以分享一下经验吗？
这是一个尚未完全阐述的想法：
也许您可以使用四重分支树，其中包含二元组值（高度和宽度），每个值代表一个矩形。
一个节点（w，h）有4个子节点：
(<w, <h) - 包含更小宽度和更小高度的矩形(>=w, <h) - 包含具有更大宽度和更小高度的矩形(<w, >=h) - 包含宽度更小、高度更大的矩形(>=w, >=h) - 包含具有更大宽度和更大高度的矩形
当您下降到 (w, h) 矩形节点为您的 (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)。
还不确定删除和平衡。但我几乎可以肯定也有解决方案。
假设我有一组矩形（尺寸不同或相同）。
- 任务是从集合中找到（并移除）大于或等于给定矩形的矩形。
- 它也应该是集合中可以包含给定矩形的最小矩形。
这很容易通过线性搜索/更新在 O(n) 时间内解决，但是否有可能获得更好的结果？ 我认为 O(log n) 是最优的。 插入和删除也必须比 O(n) 快，因为这对我的情况有用。
是否可以通过不寻找最佳矩形来创建任何捷径，而是将第二个限制放宽为： "It should also be one of the smallest rectangles that can encompass the given rectangle"-
我正在考虑使用 Z-order curve（属于 width/height）并将其用作一维索引并将其与树结合。 那行得通吗？还是会浪费太多？
另一种方法是使用一个轴使用树，然后线性测试另一个。
有没有人做过类似的事情，可以分享一下经验吗？
这是一个尚未完全阐述的想法：
也许您可以使用四重分支树，其中包含二元组值（高度和宽度），每个值代表一个矩形。
一个节点（w，h）有4个子节点：
(<w, <h)- 包含更小宽度和更小高度的矩形(>=w, <h)- 包含具有更大宽度和更小高度的矩形(<w, >=h)- 包含宽度更小、高度更大的矩形(>=w, >=h)- 包含具有更大宽度和更大高度的矩形
当您下降到 (w, h) 矩形节点为您的 (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)。 还不确定删除和平衡。但我几乎可以肯定也有解决方案。