Scandinavian thins on top of cake : new and improved algorithms for stacking and packing

H. Alt, E.M. Arkin, A. Efrat, G. Hart, Ferran Hurtado, I. Kostitsyna, A. Kröller, J.S.B. Mitchell, V. Polishchuk

Research output: Contribution to journalArticleAcademicpeer-review

1 Citation (Scopus)

Abstract

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.
Original languageEnglish
Pages (from-to)689-714
Number of pages26
JournalTheory of Computing Systems
Volume54
Issue number4
DOIs
Publication statusPublished - 2014
Externally publishedYes

Fingerprint

Dive into the research topics of 'Scandinavian thins on top of cake : new and improved algorithms for stacking and packing'. Together they form a unique fingerprint.

Cite this