Scandinavian Thins on Top of Cake: New and Improved Algorithms for Stacking and Packing
2014 (English)In: Theory of Computing Systems, ISSN 1432-4350, Vol. 54, no 4, 689-714 p.Article in journal (Refereed) PublishedText
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.
Place, publisher, year, edition, pages
2014. Vol. 54, no 4, 689-714 p.
Computational geometry – Enclosure – Packing
IdentifiersURN: urn:nbn:se:liu:diva-128019DOI: 10.1007/s00224-013-9493-9OAI: oai:DiVA.org:liu-128019DiVA: diva2:928741