Framework for $\exists \mathbb{R}$-Completeness of Two-Dimensional Packing Problems

Résumé 0

The aim in packing problems is to decide if a given set of pieces can beplaced inside a given container. A packing problem is defined by the types ofpieces and containers to be handled, and the motions that are allowed to movethe pieces. The pieces must be placed so that in the resulting placement, theyare pairwise interior-disjoint. We establish a framework which enables us toshow that for many combinations of allowed pieces, containers and motions, theresulting problem is $\exists \mathbb{R}$-complete. This means that the problemis equivalent (under polynomial time reductions) to deciding whether a givensystem of polynomial equations and inequalities with integer coefficients has areal solution. We consider packing problems where only translations are allowed as themotions, and problems where arbitrary rigid motions are allowed, i.e., bothtranslations 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. Restrictedto translations, we show that the following problems are $\exists\mathbb{R}$-complete: (i) pieces bounded by segments and hyperbolic curves tobe packed in a square, and (ii) convex polygons to be packed in a containerbounded by segments and hyperbolic curves.