在直线多边形中包装矩形

给定一组轴对齐矩形（可旋转90度）和直线多边形，我想确定矩形是否可以全部打包到此多边形中，并且如果可能的话，找到一个任意的包装。在直线多边形中包装矩形

这是NP难吗？任何假设都可以解决这个问题吗？（例如限制多边形是正交凸的）任何类型的引用都会很好吗？

来源

2017-03-01 Woofas

是的，即使容器多边形本身是一个矩形也是NP（参见[Korf 2003]（http://www.aaai.org/Papers/ICAPS/2003/ICAPS03-029.pdf））。存在各种各样的近似算法，只是谷歌“矩形包装”。 –

@ n.m。这很有用，如果你的评论变成了答案，我会满意的，如果你引用关于将矩形包装转换成包装密封以证明NP硬度的部分，更有帮助，谢谢！ – Woofas

我自己并不完全理解证明，没有太多时间按照我的方式工作。 –

关于包装矩形，usaco也有类似的任务。我只通过回溯来解决它。 Here是解决方案的说明

来源

2017-03-01 11:45:33 oybek

链接已经死亡。 – zwcloud

是的，即使容器多边形本身是矩形（请参阅Korf 2003），也是NP。

存在各种各样的近似算法，只是谷歌“矩形包装”。

给出一个bin包装的实例，我们可以生成一个相应的矩形打包实例，如下所示。对于装箱问题中的每个数字，我们生成一个单位高度的矩形，其宽度是数字的值。因此每个数字都会生成一个宽度和单位高度的条。我们还生成一个封闭的矩形，其高度为个垃圾箱，其宽度是垃圾箱的容量。因此，每个箱对应于包围的矩形的水平条。在产生的矩形包装问题中，必须将每个条带分配给包围的矩形的行（bin），使得分配给每一行（bin）的条带的宽度（数字）总和不为超过封闭矩形的宽度（容器容量）。请注意，带是定向的，不能旋转。因此，这个矩形包装的问题相当于原装装箱问题的问题。如果我们可以解决多项式时间中的任何矩形填充问题，那么我们可以在多项式时间内解决任何装箱问题。因此，矩形包装是NP-hard，，因为它也在NP中，所以它是NP-complete。

来源

2017-03-01 11:49:13

在直线多边形中包装矩形

回答

相关问题