algorithm - 将矩形划分为更小的包含 1 个点的矩形，最大化荒地面积

Question

给定一个包含 P 个点的矩形 R，与轴正交，点是自然数。

地 block 是一个矩形，它:

• 完全在R中
• 边与轴正交
• 里面正好包含一个点
• 它的边必须与 R 的边相邻或包含来自 P 的点

找到一种算法来找到 R 内的所有可能的地 block ，使它们的总面积最小(最大化荒地面积)。

示例:多种划分方式之一，5 个点(*)，2 个包裹

    R
|-----------------------------------------------|
|                   |                   |       |
|                   |                   |   *   |
|                   *                   |       |
|                   |                   *       |
|                   |               *   |       |
|                   |                   |       |
|                   |                   |       |
|                   |-----------*-------|       |
|    wastelands                         |       |
|                                       |       |
|                                       |       |
|-----------------------------------------------|

首先，让我们跳过优化(最大/最小)。有什么好的分割矩形的方法吗？

编辑

看起来它可能是 NP-hard。我从这个问题的发起者那里得到了一些反馈，找到所有可能的包裹是没有意义的。 我认为唯一的方法是使用一些启发式方法(例如，找到最大的地 block 或包含最多点的地 block )并检查结果。

Answer 1

我可以为初学者想到一个回溯和指数级困难的方法。您按某种顺序选择点，每次执行以下任一操作:

1-决定通过一条竖线 2- 决定通过水平线 3- 决定忽略

直到您遇到 3^n 种不同的情况。

对于您自己的应用程序，您可以考虑在每次迭代时应用一些边界条件，例如，验证您是否最终得到一个内部没有点的包裹，然后回溯。