TY - JOUR
T1 - Scandinavian thins on top of cake
T2 - New and improved algorithms for stacking and packing
AU - Alt, Helmut
AU - Arkin, Esther M.
AU - Efrat, Alon
AU - Hart, George
AU - Hurtado, Ferran
AU - Kostitsyna, Irina
AU - Kröller, Alexander
AU - Mitchell, Joseph S.B.
AU - Polishchuk, Valentin
N1 - Publisher Copyright:
© Springer Science+Business Media New York 2013.
PY - 2014/5
Y1 - 2014/5
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 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.
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 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.
KW - Computational geometry
KW - Enclosure
KW - Packing
UR - http://www.scopus.com/inward/record.url?scp=85028193410&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85028193410&partnerID=8YFLogxK
U2 - 10.1007/s00224-013-9493-9
DO - 10.1007/s00224-013-9493-9
M3 - Article
AN - SCOPUS:85028193410
SN - 1432-4350
VL - 54
SP - 689
EP - 714
JO - Theory of Computing Systems
JF - Theory of Computing Systems
IS - 4
ER -