Framework for er-completeness of two-dimensional packing problems
Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
We show that many natural two-dimensional packing problems are algorithmically equivalent to finding real roots of multivariate polynomials. A two-dimensional packing problem is defined by the type of pieces, containers, and motions that are allowed. The aim is to decide if a given set of pieces can be placed inside a given container. The pieces must be placed so that in the resulting placement, they are pairwise interior-disjoint, and only motions of the allowed type can be used to move them there. We establish a framework which enables us to show that for many combinations of allowed pieces, containers, and motions, the resulting problem is ER-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. A full version of this extended abstract is available on https://arxiv.org/abs/1704.06969.
Original language | English |
---|---|
Title of host publication | Proceedings - 2020 IEEE 61st Annual Symposium on Foundations of Computer Science, FOCS 2020 |
Publisher | IEEE Computer Society Press |
Publication date | 2020 |
Pages | 1014-1021 |
Article number | 9317895 |
ISBN (Electronic) | 9781728196213 |
DOIs | |
Publication status | Published - 2020 |
Event | 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020 - Virtual, Durham, United States Duration: 16 Nov 2020 → 19 Nov 2020 |
Conference
Conference | 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020 |
---|---|
Land | United States |
By | Virtual, Durham |
Periode | 16/11/2020 → 19/11/2020 |
Sponsor | IEEE Computer Society Technical Committee on Mathematical Foundations of Computing |
- Existential Theory of the Reals, Geometric Packing
Research areas
ID: 258402025