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

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
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) Published
Resource type
Text
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

Altmetric score

Total: 92 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf