n个矩形的交集 - 恰好有k个矩形相交时的最大区域数

Question

n个矩形的交集 - 恰好有k个矩形相交时的最大区域数

algorithmgeometrycomplexity-theorycomputational-geometry

3

想象一下n个轴对齐的矩形（由其位置(x,y)、宽度和高度指定）。这些矩形以一种方式对齐，使得第i个矩形必然与第(i + 1)个相交。例如，让n = 3，则1必然与2相交，2与3相交。需要注意的是，这不是传递性；3可以与1相交，但没有保证（参见图示两个有效的对齐示例）。

现在我要找的是恰好有k = 2、...、n个矩形相交的最大可能区域数（这些区域在图中显示）。换句话说，我正在寻找一种最坏情况下的n个矩形对齐方式，使得恰好k个矩形相交的区域数量达到最大值。理论上，恰好k个矩形相交的最大可能区域数是n/k（二项式系数）。然而，由于不可能对齐（并绘制）n≥4的矩形，以便在最坏情况下存在n/k个区域恰好相交k个矩形，因此该公式仅在几何上对n<4有效。

图中的第一个子图显示了n = 3的最坏情况对齐。恰好有3个矩形相交的区域有3个，恰好有3个矩形相交的区域有1个。第二个子图也显示了三个矩形的有效对齐方式，但这不是最坏情况下的对齐方式，例如，没有恰好有三个矩形相交的区域。

- MaxWell

你能详细解释一下输入和期望输出是什么吗？ - m69 ''snarky and unwelcoming''

1

我认为这不是一个几何问题：重要的是第i个矩形是否与第j个矩形相交，如果你抽象出这个信息，你就得到了一个组合问题。我认为它归结为计算某些年轻的斜表，其中每个表项（i，j）表示第i个矩形是否与第j个矩形相交。如果第i个矩形不与第j个矩形相交，则第i个矩形不与第j + 1个矩形相交的传递性被编码在斜表的本质中。长度为k的区域对应于宽度为k的斜表行。 - Michael

@Michael 非常感谢你提供的提示，听起来非常有前途！我会仔细研究并给你反馈。 - MaxWell

我不清楚为什么这不是一个几何问题。如果第i个和第j个矩形相交，其他矩形为什么不起任何作用呢？如果1与2相交，3是否与1和2相交很重要？据我所知，Young's Skew-Tableaux用于可视化非负整数的分区。因此，例如，3的分区是3、1 + 2、1 + 1 + 1，p（3）= 3。 n的分区如何与我的问题相关？如果我将3的分区可视化，我会得到一个区域，其中有3个矩形��叠，k = 2的1个区域和k = 1的1个区域...? - MaxWell

1

@MaxWell，那太长了，让我把它放到一个答案中。 - Michael

显示剩余5条评论

2个回答

0

创建一个矩阵，在这个矩阵中，如果矩形i和矩形j相交，则单元格Aij为1，否则为0。该矩阵对称。

现在注意到许多靠近对角线的1表示相邻对齐的矩形之间的相交更多。

"最坏"情况即矩形相互交叉的数量k是最大的，在矩阵中用k个连续的1表示，中间没有0。您可以考虑对角线后面的元素。这样就满足了"矩形i与矩形j相交"的属性。

问题在于如何交换行和列以实现此结果。这可能是一个矩阵带宽缩减问题。例如，参见this和this。

您还可以为自己的特殊情况生成算法。请注意，这可能是一个NP问题，而且可能存在多种解决方案。

- Ripi2

我正在寻找一个全局解决方案，而不是针对n个矩形的特定对齐方式。因此，我无法构建矩阵，因为我不知道矩形的坐标。使用您的方法，我认为我被迫测试A的所有可能配置？ - MaxWell

@MaxWell 如果您不知道坐标，那么如何区分交叉口和相邻的路口呢？ - Ripi2

@MaxWell，你没有回答我的关于坐标的问题；如果没有它们，你如何找到区域？关于那个理论上的最大值，是要求还是你自己的想法？ - Ripi2

我只需要可能性的数量；即恰好有 k 个矩形重叠的区域的最大数量。如果我能构造出这样一个最坏情况的对齐方式，我就知道了最大值。这就是想法。 - MaxWell

是的，看起来是这样。我会更新我的问题。无论如何，谢谢。 - MaxWell

显示剩余4条评论

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Michael · Accepted Answer

一个错误的答案；只因其可能或可能不有用的方法而未被删除。

几何数据 - 即矩形相交 - 可以被抽象出来：重要的是以下属性：

属性P：如果矩形i和j相交，则i也与i + 1，...，j-1相交。

如果您对问题的表示编码了P，则起始的矩形就不再重要了。

现在，我们如何记录哪些矩形相交？一种方法是使用节点为矩形，边表示相交的图形，但这并不是很有用，因为上述属性P在图中不明显。更好的方法是设置以下矩阵：

将第i个矩形表示为矩阵A的第i行，该行在A(i,i)处之前为0，在A(i,i)到A(i,i+m)处为1，其中i+m是与矩形i相交的最远矩形的索引。也就是说，A有n行，每一行对应原始矩形中的一个，它由0和1组成，对于j>i的A(i,j)，当且仅当矩形i和j相交时为1。对于j

现在，我们有恰好k个相交矩形的面积是什么意思？我声称上述矩阵通过具有恰好k个1的列来表示。为什么？假设您的区域是矩形i+1,...,i+k的交集。看一下矩阵条目A(i+k,i+k)。它上面的列在1+1到i+k的行中为1，否则为0。

上述矩阵看起来与杨表类似，因此有这个注释。但是，相似性是表面的，因为它不是源自分区。

现在剩下的就是最大化在A中恰好有k个1的列的数量。我认为最好的矩阵是每行恰好有k个1的矩阵，这将给出原始问题n的答案。显然，答案是错误的，所以我在这里缺少了什么。啊啊啊！