You are cordially invited to our first Monday Lecture &
Colloquium since Corona crisis stopped our curriculum. Zoom - Invitation will follow Time: Monday, October 19th - 14:15 h Lecture: Mikkel Abrahamsen (University of
Copenhagen) Title: A framework for ∃R-completeness of two-dimensional packing problems Abstract: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 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 ∃R-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. We
consider packing problems where only translations are allowed
as the motions, and problems where arbitrary rigid motions are
allowed, i.e., both translations and rotations. When rotations
are 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 hyperbolic
curves into a square, - convex polygons into a container
bounded by line segments and hyperbolic curves. Restricted to
translations, we show that the following combinations are
∃R-complete: - objects bounded by segments and hyperbolic
curves into a square, - convex polygons into a container
bounded by segments and hyperbolic curves. Joint work by
Mikkel Abrahamsen, Tillmann Miltzow, and Nadja Seiferth. The
paper has been accepted for FOCS.
Break : Wherever you are. Time: Monday, October 19th - 16:00 h s.t. Colloquium: Tillmann Miltzow (Utrecht University) Title: A practical algorithm with performance guarantees for the art-gallery problem Abstract:Given a closed simple polygon P, we
say two points p,q see each other if the segment pq is fully
contained in P. The art gallery problem seeks a minimum size
set G⊂P of guards that sees P completely. The only known
algorithm to solve the art gallery problem exactly is
attributed to Sharir and uses algebraic methods. As the art
gallery problem is ∃R-complete, it seems impossible to avoid
algebraic methods without additional assumptions. Joint work by Simon Hengeveld & Tillmann Miltzow. |