3 ms·
The article doesn't really make it clear that there's an actual result, showing that many two-dimensional packing problems are equivalent to finding real roots
by kens 6y ago
The article doesn't really make it clear that there's an actual result, showing that many two-dimensional packing problems are equivalent to finding real roots of multivariate polynomials, and many problems are ∃ℝ-complete. (∃ℝ-complete is kind of like NP-complete for real numbers. The ∃ℝ complexity class lies between NP and PSPACE.)
The paper shows that various specific problems are ∃ℝ-complete. One such problem is packing simple polygons with at most 8 corners into a square, with rotation and translation. (E.g. cutting polygonal cookies out of dough.) Another is packing objects bounded by segments and hyperbolic curves into a square with translation but not rotation.
Random fact from the paper: there's no agreement on how to pronounce ∃ℝ-complete.
The "Existential Theory of the Reals" is (ambiguiously) the ∃ℝ complexity class, a formal language, and an algorithmic problem. More info: https://en.wikipedia.org/wiki/Existential_theory_of_the_reals https://en.wikipedia.org/wiki/Existential_theory_of_the_real...
Disclaimer: I didn't know anything about ∃ℝ before looking into this, but thought others might be interested in a bit of background.