Framework for er-completeness of two-dimensional packing problems

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-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 languageEnglish
Title of host publicationProceedings - 2020 IEEE 61st Annual Symposium on Foundations of Computer Science, FOCS 2020
PublisherIEEE Computer Society Press
Publication date2020
Pages1014-1021
Article number9317895
ISBN (Electronic)9781728196213
DOIs
Publication statusPublished - 2020
Event61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020 - Virtual, Durham, United States
Duration: 16 Nov 202019 Nov 2020

Conference

Conference61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020
LandUnited States
ByVirtual, Durham
Periode16/11/202019/11/2020
SponsorIEEE Computer Society Technical Committee on Mathematical Foundations of Computing

    Research areas

  • Existential Theory of the Reals, Geometric Packing

ID: 258402025