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.
|Title of host publication||Fun with algorithms|
|Subtitle of host publication||6th International Conference, FUN 2012, Venice, Italy, June 4-6, 2012. Proceedings|
|Editors||Evangelos Kranakis, Danny Krizanc, Flaminia Luccio|
|Place of Publication||Berlin|
|Number of pages||12|
|Publication status||Published - 2012|
|Name|| Lecture Notes in Computer Science (LNCS)|