TY - JOUR

T1 - Scandinavian thins on top of cake : new and improved algorithms for stacking and packing

AU - Alt, H.

AU - Arkin, E.M.

AU - Efrat, A.

AU - Hart, G.

AU - Hurtado, Ferran

AU - Kostitsyna, I.

AU - Kröller, A.

AU - Mitchell, J.S.B.

AU - Polishchuk, V.

PY - 2014

Y1 - 2014

N2 - 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 for the 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.

AB - 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 for the 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.

U2 - 10.1007/s00224-013-9493-9

DO - 10.1007/s00224-013-9493-9

M3 - Article

VL - 54

SP - 689

EP - 714

JO - Theory of Computing Systems

JF - Theory of Computing Systems

SN - 1432-4350

IS - 4

ER -