liu.seSearch for publications in DiVA
Change search
ReferencesLink to record
Permanent link

Direct link
Scandinavian Thins on Top of Cake: New and Improved Algorithms for Stacking and Packing
Institut für Informatik, Freie Universität, Berlin, Germany .
Applied Mathematics and Statistics, Stony Brook University, Stony Brook, USA .
Computer Science, The University of Arizona, Tucson, USA .
Show others and affiliations
2014 (English)In: Theory of Computing Systems, ISSN 1432-4350, Vol. 54, no 4, 689-714 p.Article in journal (Refereed) PublishedText
Abstract [en]

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.
Keyword [en]
Computational geometry – Enclosure – Packing
National Category
Computer Science
Identifiers
URN: urn:nbn:se:liu:diva-128019DOI: 10.1007/s00224-013-9493-9OAI: oai:DiVA.org:liu-128019DiVA: diva2:928741
Available from: 2016-05-16 Created: 2016-05-16 Last updated: 2016-05-26

Open Access in DiVA

No full text

Other links

Publisher's full text
Computer Science

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Altmetric score

Total: 90 hits
ReferencesLink to record
Permanent link

Direct link