论文标题
$ \存在的框架\ Mathbb {r} $ - 二维包装问题的完整性
Framework for $\exists \mathbb{R}$-Completeness of Two-Dimensional Packing Problems
论文作者
论文摘要
包装问题的目的是确定是否可以在给定的容器中放置一组给定的件。包装问题由要处理的碎片和容器的类型定义，以及允许移动零件的运动。必须放置这些零件，以使其在由此产生的位置中，它们是成对的内部界限。我们建立了一个框架，使我们能够证明，对于允许的零件，容器和动作的许多组合，结果问题是$ \ comests \ mathbb {r} $ - 完整。这意味着该问题是等效的（在多项式时间缩短的情况下），可以决定给定的多项式方程组和具有整数系数的不等式系统是否具有真实的解决方案。 我们考虑只允许翻译作为动作的包装问题，以及允许任意刚性动作的问题，即翻译和旋转。当允许旋转时，我们表明它是$ \ Mathbb {r} $ - 完整的问题，以决定是否可以将一组凸形多边形（每个凸角都有$ 7 $角）包装到一个正方形中。仅限于翻译，我们表明以下问题是$ \ Mathbb {r} $ - 完整：（ i）由细分市场和双曲线曲线包围的零件，并且要包装在正方形中，并且（ii）凸出的多边形将包装在容器中，以段和弱曲线和多余的曲线界定。
The aim in packing problems is to decide if a given set of pieces can be placed inside a given container. A packing problem is defined by the types of pieces and containers to be handled, and the motions that are allowed to move the pieces. The pieces must be placed so that in the resulting placement, they are pairwise interior-disjoint. We establish a framework which enables us to show that for many combinations of allowed pieces, containers and motions, the resulting problem is $\exists \mathbb{R}$-complete. This means that the problem is equivalent (under polynomial time reductions) to deciding whether a given system of polynomial equations and inequalities with integer coefficients has a real solution. We consider packing problems where only translations are allowed as the motions, and problems where arbitrary rigid motions are allowed, i.e., both translations and rotations. When rotations are allowed, we show that it is an $\exists \mathbb{R}$-complete problem to decide if a set of convex polygons, each of which has at most $7$ corners, can be packed into a square. Restricted to translations, we show that the following problems are $\exists \mathbb{R}$-complete: (i) pieces bounded by segments and hyperbolic curves to be packed in a square, and (ii) convex polygons to be packed in a container bounded by segments and hyperbolic curves.
