2

我有这个问题：给定一组矩形 {R1,R2...Rn} 和一个新矩形 Rq，找到放置 Rq 的位置，使其相交（不管面积多少）矩形的最大数量集。我正在寻找一个不涉及太复杂数据结构的简单解决方案，但是，非常感谢任何有效的答案，谢谢！

4

1 回答 1

0

这是一个O(n^2)或O(n (log n + m))（仅平均情况）复杂度算法（其中m是相交矩形的最大数量）。方法见后O(n log n)文。

第一个想法是考虑到有n地方可以寻找解决方案。也就是说，对于每个矩形Ri，Ri最右边的矩形相交Rq的情况是候选解。

您将从左到右扫描。将矩形按最小 x 坐标的顺序添加到缓冲区容器，以及优先级队列（基于最大 x 坐标）。添加每个矩形时，还要检查需要删除哪些矩形（基于优先级队列），以便Rq如果您暂时忽略 y 轴，缓冲区中的矩形范围可以与矩形相交。

在将每个矩形添加到缓冲区之前，您可以考虑如果需要相交Ri，缓冲区中可以相交多少个矩形（与相交的最右边的矩形）。这可以在线性时间内完成。RqRiRiRq

因此总体复杂度为O(n^2)。

通过对存储在缓冲区中的任何矩形节点使用区间树，可以改进算法的运行时间。由于 Wikipedia 提供了大量关于这方面的信息，以及它是如何实现的，我不会在这里解释它是如何工作的，特别是因为它的平衡可能相当复杂。这会将平均复杂度提高到O(n (log n + m))，答案在哪里- 相交矩形的最大数量（在最坏的情况下m仍然可能一样大）。n这是由于查询间隔树的算法复杂性（O(log n + m)每次查询的时间）。最坏的情况仍然是O(n^2)，因为m对于返回的结果数（对于区间树），可能高达O(n)，即使答案不是n.

这里遵循一种随O(n log n)时间变化的方法，但相当复杂。

除了将矩形存储为排序数组、自平衡二叉搜索树（仅基于最小 y）或区间树，矩形还可以存储在自定义数据结构中。

考虑自平衡二叉搜索树（基于最大 y）。我们可以为此添加一些元数据。值得注意的是，由于我们尝试最大化缓冲区中相交的矩形，并不断寻找随着缓冲区从左到右扫描时最大值如何变化，如果缓冲区中的每个矩形都是最底部的，我们可以考虑相交的矩形数量长方形。

如果我们可以存储矩形的数量，我们也许可以更快地查询它。

解决方案是以不同的方式存储它，以降低更新成本。二叉搜索树有许多边。假设每个节点应该知道如果该节点是要相交的最底部矩形，则可以相交多少个矩形。相反，我们可以存储与每条边任一侧的节点相交的矩形数量的变化（称为diff）。例如，对于以下树（具有最小和最大 y 的矩形）：

     (3,4)
      / \
   (2,3) (5,6)

对于Rq高度为 2 的情况，如果(2,3)是最底部的，我们总共可以相交 2 个矩形，对于(3,4)，它是 2，对于(5,6)，它是 1。

因此，edges'diff可以是 0 和 -1，代表答案从孩子到父母的变化。

使用权重，如果每个节点也在其子树中存储子路径的最大总和（称为 this maxdiff），我们可以快速找到最大数。对于叶子，它是 0，但是对于(3,4)，0 和 -1 的最大值是 0，因此，我们可以将 0 存储为根节点中子路径的边的最大和。

因此，我们知道最优答案比根节点的答案多 0。我们可以找到根节点的答案，但保留更多的元数据。

但是，所有这些元数据都可以及时查询和更新log n。这是因为当我们添加一个矩形时，将其添加到自平衡二叉搜索树需要log n时间，因为我们可能需要进行log n旋转。当我们进行旋转时，我们可能需要更新边缘以及maxdiff受影响节点上的权重 - 但是这是O(1)针对每次旋转的。

此外，diff需要更新额外矩形对边缘的影响。但是，最多O(log n)边必须更新，具体来说，如果我们通过新矩形的 min y 和 max y 搜索树，我们会找到所有需要更新的边（尽管遍历的边是否必须更新取决于我们是带左孩子还是右孩子——这里需要一些仔细的工作来确定确切的规则）。

删除一个矩形正好相反，所以需要O(log n)时间。

这样，我们可以及时更新缓冲区，O(log n)及时查询O(log n)，整体算法复杂度为O(n log n).

注意：要找到缓冲区中相交的最大矩形，我们使用maxdiff，这是最优答案与根节点答案之间的差异。要找到实际答案，我们必须找到二叉搜索树中最低排序矩形的答案与根节点之间的差异。这很容易及时完成，沿着最左边的路径走，并在边缘O(log n)总结。diff最后，在排序最低的矩形上找到答案。这是通过存储按最小 y 排序的第二个自平衡二叉搜索树来完成的。如果按最大 y 排序时最底部的矩形是排序最低的矩形，我们可以使用它来查找相交的矩形的数量。

更新这个额外的 BST 和查询也需要O(log n)时间，所以这个额外的工作不会改变整体的复杂性。

于 2012-09-18T08:59:20.767 回答