Scandinavian thins on top of cake: on the smallest one-size-fits-all box

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

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-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.
Original languageEnglish
Title of host publicationFun with algorithms
Subtitle of host publication6th International Conference, FUN 2012, Venice, Italy, June 4-6, 2012. Proceedings
EditorsEvangelos Kranakis, Danny Krizanc, Flaminia Luccio
Place of PublicationBerlin
PublisherSpringer
Chapter5
Pages16-27
Number of pages12
ISBN (Electronic)978-3-642-30347-0
ISBN (Print)978-3-642-30346-3
DOIs
Publication statusPublished - 2012
Externally publishedYes

Publication series

Name Lecture Notes in Computer Science (LNCS)
Volume7288
ISSN (Print)0302-9743

Fingerprint Dive into the research topics of 'Scandinavian thins on top of cake: on the smallest one-size-fits-all box'. Together they form a unique fingerprint.

Cite this