## Mikkel Abrahamsen ; Tillmann Miltzow ; Nadja Seiferth - Framework for $\exists \mathbb{R}$-Completeness of Two-Dimensional Packing Problems

theoretics:9369 - TheoretiCS, April 26, 2024, Volume 3 - https://doi.org/10.46298/theoretics.24.11
Framework for $\exists \mathbb{R}$-Completeness of Two-Dimensional Packing ProblemsArticle

Authors: Mikkel Abrahamsen ; Tillmann Miltzow ; Nadja Seiferth

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.

Volume: Volume 3
Published on: April 26, 2024
Accepted on: February 15, 2024
Submitted on: April 21, 2022
Keywords: Computer Science - Computational Geometry,Computer Science - Computational Complexity,Computer Science - Discrete Mathematics,Computer Science - Data Structures and Algorithms