Scandinavian thins on top of cake: New and improved algorithms for stacking and packing

We show how to compute the smallest rectangle that can enclose any polygon, from a given set of polygons, in nearly linear time; we also present a PTAS forthe problem, as well as a linear-time algorithm for the case when the polygons are rectangles themselves.We prove that finding a smallest convex polygon that encloses any of the given polygons is NP-hard, and give a PTAS for minimizing the perimeter of the convex enclosure. We also give efficient algorithms to find the smallest rectangle simultaneously enclosing a given pair of convex polygons.