BEGIN:VCALENDAR
CALSCALE:GREGORIAN
PRODID:iCalendar-Ruby
VERSION:2.0
BEGIN:VEVENT
DESCRIPTION: We show that many natural two-dimensional packing problems are
algorithmically equivalent to finding real roots of multivariate polynomia
ls. A two-dimensional packing problem is defined by the type of pieces\, co
ntainers\, and motions that are allowed. The aim is to decide if a given se
t of pieces can be placed inside a given container. The pieces must be plac
ed so that they are pairwise interior-disjoint\, and only motions of the al
lowed type can be used to move them there. We establish a framework which e
nables us to show that for many combinations of allowed pieces\, containers
\, and motions\, the resulting problem is ∃R-complete. This means that the
problem is equivalent (under polynomial time reductions) to deciding whethe
r a given system of polynomial equations and inequalities with integer coef
ficients has a real solution. We consider packing problems where only trans
lations are allowed as the motions\, and problems where arbitrary rigid mot
ions are allowed\, i.e.\, both translations and rotations. When rotations a
re allowed\, we show that the following combinations of allowed pieces and
containers are ∃R-complete: - simple polygons\, each of which has at most 8
corners\, into a square\, - convex objects bounded by line segments and hy
perbolic curves into a square\, - convex polygons into a container bounded
by line segments and hyperbolic curves. Restricted to translations\, we sho
w that the following combinations are ∃R-complete: - objects bounded by seg
ments and hyperbolic curves into a square\, - convex polygons into a contai
ner bounded by segments and hyperbolic curves. Joint work by Mikkel Abraham
sen\, Tillmann Miltzow\, and Nadja Seiferth. The paper has been accepted fo
r FOCS.
DTSTAMP:20201007T185000
DTSTART:20201019T141500
CLASS:PUBLIC
LOCATION:online
SEQUENCE:0
SUMMARY:Mikkel Abrahamsen (University of Copenhagen): A framework for ∃R-co
mpleteness of two-dimensional packing problems
UID:107734638@www.facetsofcomplexity.de
URL:http://www.facetsofcomplexity.de/monday/20201019-L-1st-week-WS-2020-Abr
ahamsen.html
END:VEVENT
END:VCALENDAR