TY - GEN
T1 - Scandinavian thins on top of cake
T2 - 6th International Conference on Fun with Algorithms, FUN 2012
AU - Arkin, Esther M.
AU - Efrat, Alon
AU - Hart, George
AU - Kostitsyna, Irina
AU - Kröller, Alexander
AU - Mitchell, Joseph S.B.
AU - Polishchuk, Valentin
PY - 2012
Y1 - 2012
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.
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.
UR - https://www.scopus.com/pages/publications/84861991327
U2 - 10.1007/978-3-642-30347-0_5
DO - 10.1007/978-3-642-30347-0_5
M3 - Conference contribution
AN - SCOPUS:84861991327
SN - 9783642303463
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 16
EP - 27
BT - Fun with Algorithms - 6th International Conference, FUN 2012, Proceedings
Y2 - 4 June 2012 through 6 June 2012
ER -