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.mi.fu-berlin.de
URL:https://www.mi.fu-berlin.de/en/facetsofcomplexity/monday/20201019-L-1st
 -week-WS-2020-Abrahamsen.html
END:VEVENT
END:VCALENDAR