找到两个覆盖所有点的最小区域的矩形

Question

你得到一个点,在数组中未分类.您应该找到两个覆盖所有点的矩形,它们不应重叠.矩形的边缘应平行于x或y纵坐标.
该程序应返回所有这些点所覆盖的最小区域.第一个矩形的区域+第二个矩形的区域.

我试图解决这个问题.我按X纵坐标对点进行排序,第一个是第一个矩形的最左边一个.当我们通过积分时,我们找到最高点和最低点.我在想,当两个点之间的差异乘以x时,这意味着第一个点是第一个矩形中最右边的一个,第二个点是第二个矩形中最左边的一个.
它应该在第一个示例中给出点时起作用,但是,如果示例是第二个示例则它不起作用.因为它会返回类似这样的东西,这是错误的:

这应该是正确的:

然后我想要做两次排序,只是,第二次用Y纵坐标做,然后比较两个总面积.当点按x排序并且点按y排序且较小区域是正确答案时的区域.

Answer 1

第一个观察结果是矩形的任何边都必须接触其中一个点。未接触点的边缘可能会被拉回，从而导致面积减少。

给定 n 个点，因此 left1、right1、bottom1、top1、left2、right2、bottom2 和 top2 总共有 n 个选择。这已经给出了一个简单的 O(n^8) 算法：尝试所有可能的分配并记住给出最小总面积的分配 (right1 - left1)(top1 - Bottom1) + (right2 - left2)(top2 - Bottom2)。事实上，您可以跳过任何右 < 左或上 < 下的组合。这提供了加速，但它不会改变 O(n^8) 界限。

另一个观察结果是边缘应保持在所有点的最小和最大 X 和 Y 边界内。查找任意点的最小和最大 X 和 Y 值。将这些称为 minX、maxX、minY 和 maxY。至少有一个矩形需要分别在这些级别上具有其左、右、下和上边缘。

因为 minx、maxX、minY 和 maxY 必须分配给两个矩形之一，并且恰好有 2^4 = 16 种方法可以执行此操作，因此您可以尝试四种可能的分配中的每一种，并按上面分配的剩余坐标进行操作。这给出了 O(n^4) 算法：O(n) 获取 minX、maxX、minY 和 maxY，然后 O(n^4) 为 minX、maxX 的 16 个赋值中的每一个填充四个未赋值的变量， minY 和 maxY 为八个边缘坐标。

到目前为止，我们忽略了矩形不重叠的要求。为了适应这一点，我们必须确保至少满足以下四个条件之一：

1. Y 坐标 h 处的水平线，其中 top1 <= h <= Bottom2
2. Y 坐标 h 处的水平线，其中 top2 <= h <= Bottom1
3. X 坐标 w 处的垂直线，其中 right1 <= h <= left2
4. X 坐标 w 处的垂直线，其中 right2 <= h <= left1

当且仅当所有四个条件同时为假时，两个矩形才会重叠。这允许我们跳过候选解决方案，提供加速但不改变渐近界限 O(n^4)。请注意，我们需要专门检查此条件，否则最佳解决方案可能会重叠（练习：展示这样的示例）。

让我们试着再节省一些时间。假设根据上面的条件#1，我们有不重叠的矩形。那么h有n个选择；我们可以尝试这 n 个选择中的每一个，然后通过找到结果两半中点的最小和最大坐标来确定结果选择的面积。通过尝试 h 的所有 n 个选择，我们可以确定“最佳情况”垂直分割。我们不需要尝试条件#2，因为唯一的区别在于矩形的顺序是任意的。我们还必须尝试水平分割的条件 #3。这建议使用 O(n^2) 算法：

1. 对于每个点，选择 h = point.y
2. 将点分成 point.y <= h 和 point.y > h 的组。
3. 找到两个点子集的最小和最大 X 和 Y 坐标。
4. 计算两个矩形的面积之和。
5. 记住上面得到的最小面积和对应的h。
6. 重复，但使用 w 和 X 坐标。
7. 确定垂直或水平分割是否获得了最小面积
8. 返回对应的矩形作为答案

我们还能做得更好吗？h这是 O(n^2) 而不是 O(n)，因为对于和的每个选择，w我们需要找到每个子组的最小和最大坐标。这假设对两个子组进行线性扫描。当水平/垂直扫描时，我们实际上不需要对最小和最大 X/Y 坐标执行此操作，因为这些坐标是已知的。我们需要的是解决这个问题的方法：

给定 n 个点和一个值 h，找到 Y 坐标不大于 h 的任何点的最大 X 坐标。

我上面给出的显而易见的解决方案是 O(n^2)，但是您也许可以通过巧妙地应用排序来找到 O(n log n) 解决方案，甚至可以通过一些更聪明的方法找到 O(n) 解决方案。我不会尝试这样做。

我们的解决方案是O(n^2)；理论上的最佳解决方案是 Omega(n)，因为您至少必须查看所有点。所以我们已经非常接近了，但还有改进的空间。