2020 · 24 citations · 33 references
Natural SciencesComputer ScienceMathematicsAlgorithmsCombinatoricsDiscrete MathematicsApproximation AlgorithmsCombinatorial OptimizationDisjoint SetsPacking ProblemsPlacementPolynomial OptimizationPolynomial Time ComplexityPolynomial-time AlgorithmsPolynomial-time ReductionsReductions
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.
33
A proof of the Kepler conjecture
Thomas Hales · Annals of Mathematics · 2005 · 990 citations · Full text
Natural Sciences, Astronomy, Physics +12
Some algebraic and geometric computations in PSPACE
John Canny · 1988 · 581 citations · Full text