algorithm - 找出能容纳另一个矩形的面积最小的矩形

Question

假设我有一组矩形(具有不同或相同的尺寸)。

1. 任务是从集合中找到(并移除)大于或等于给定矩形的矩形。
2. 它也应该是集合中可以包含给定矩形的最小矩形。

这很容易通过线性搜索/更新在 O(n) 时间内解决，但是否有可能获得更好的结果？我认为 O(log n) 是最优的。插入和删除也必须比 O(n) 更快，这对我的情况才有用。

是否可以通过不找到最佳矩形来创建任何捷径，而是将第二个限制放宽为:“它也应该是可以包含给定矩形的最小矩形之一”-

我一直在考虑使用 Z-order curve (宽度/高度)并用作一维索引并将其与树结合。那行得通吗？还是会浪费太多？

另一种方法是使用一个轴使用树，然后线性测试另一个。

有没有人做过类似的事情，可以分享一下他们的经验吗？

Answer 1

这是一个尚未完全阐述的想法:

也许您可以使用四重分支树，其中包含二元组值(高度和宽度)，每个值代表一个矩形。

一个节点 (w, h) 有 4 个子节点:

• (<w, <h) - 包含具有较小宽度和较小高度的矩形
• (>=w, <h) - 包含具有更大宽度和更小高度的矩形
• (<w, >=h) - 包含具有更小宽度和更大高度的矩形
• (>=w, >=h) - 包含具有更大宽度和更大高度的矩形

当您在 (w, h) 处下降时rect 节点为您的 (w2, h2) 寻找容器rect 现在有 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)。还不确定删除和平衡。但我几乎可以肯定也有解决方案。