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.