在 2d 中用 n 个其他对象覆盖形状的算法

Question

您好，我正在寻找一种用其他 n 个对象覆盖给定形状的算法。我看到了一些装箱算法，但它们试图将所有对象完美地放入给定的容器中。在我的例子中就像

如果有人可以帮助我或指导我，我可以从哪里获得有关此问题的信息，那就太好了。

Answer 1

为了部分回答这个问题，这个问题是 NP 完全的，因为它是 Partition 的几何推广问题。给定一个列表整数 {a_1,...,a_n} 和目标总和

S := ( a_1 + ... + a_n ) / 2

可以使用 n 个维度的矩形生成问题中的一个实例

1 * a_i

对于 {1,...,n} 中的每个 i 和一个大小为目标的区域

2 * S.

当且仅当 Partition 的实例允许拆分为两个总数量相等的子集时，较小的矩形可以覆盖(在本例中与适合)较大的矩形。