笛卡尔曲面项的包含算法

Question

是否有任何算法有助于最佳地找到包含分布在笛卡尔曲面上的一定数量的项目的最小矩形数（每个项目是一个具有x的点）

Answer 1

不是完整的解，只是问题的简化:假设所有点P都在大致位置，在x坐标上排序。

然后通过找出F个垂直栅栏(形式为x

然后，每个集合可以由一个轴对齐的矩形覆盖，其中集合中的第一个和最后一个点确定矩形的宽度，并且集合中具有最高y坐标的点确定高度，从而确定矩形的表面大小。

显然，现在的诀窍是选择栅栏，使栅栏的数量（以及此的矩形数）最小化，同时将所有矩形的总表面大小保持在允许的最大值以下。

编辑
可能是放置F栅栏的问题 可以使用动态规划解决。 这是我到目前为止想到的：

如果是，则最多有|P|-1个Geofence位置；这些可能会成为动态编程表中的列。动态规划表中的每一行都应该表示使用了一个额外的Geofence（请记住，我们试图找到Geofence数量最少的结果）。因此，每个单元（X，Y）将表示在前X个可用位置上精确分布Y个栅栏的最优解（就总矩形大小而言）。然而，我在看到表的相邻单元格如何（或是否）帮助确定特定单元格的值时遇到了一些问题。

编辑2：忘记这一点，我不认为动态编程方法是不可能的。这是因为我认为不可能以增量方式构建最佳解决方案（通过添加另一个点或栅栏，最佳解决方案配置可能会完全改变）。这也将排除贪婪的做法。

我能想到的唯一的想法，尽管从算法的角度来看不那么特别，是一种随机的方法，比如模拟退火来分配栅栏。它不能保证最优解，但是你应该能够非常接近最优解。

编辑3：为了回应这篇文章下的反应，我们不一定需要最好的解决方案，而是选择一个“相当好”的解决方案，并应用你现在学到的东西。

在任何情况下，您都可能需要从左到右对所有点进行排序。

一个贪婪的解决方案可能是定义第一个矩形，使其包含最左边的点。接下来，扩展矩形，使其包含右侧的点。继续添加下一个点，直到矩形超过其最大大小。在这种情况下，从一个新矩形开始，然后再次开始添加点，等等。

获得解决方案的分而治之的方法可以是从覆盖所有点的矩形开始。很明显，这个矩形超过了最大尺寸M，所以您根据某种启发法(例如，正好在中间，或者在两个后续点相距最远的点处)将它垂直分成两个更小的矩形Ml和Mr。以同样的方式递归地处理Ml和Mr，或者再次分割矩形，或者报告找到的矩形作为结果的一部分，如果它是

请注意，对于这两种方法，对于某些人为配置，结果可能会任意糟糕，但一般来说，解决方案应该是“ok”。