Many Natural Two-Dimensional Packing Problems Are Algorithmically Similar to Finding Real Roots of Polynomials
Framework for $\exists \mathbb{R}$-Completeness of Two-Dimensional Packing Problems
We show that many natural two-dimensional packing problems are algorithmically equivalent to finding real roots of multivariate polynomials.
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.