Ordered Strip Packing

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

Abstract

We study an ordered variant of the well-known strip packing problem, which is motivated by applications in visualization and typography. Our input consists of a maximum width W and an ordered list of n blocks (rectangles). The goal is to pack the blocks into rows (not exceeding W) while obeying the given order and minimizing either the number of rows or the total height of the drawing. We consider two variants: (1) non-overlapping row drawing (NORD), where distinct rows cannot share y-coordinates, and (2) overlapping row drawing (ORD), where consecutive rows may overlap vertically. We present an algorithm that computes the minimum-height NORD in O(n) time. Further, we study the worst-case tradeoffs between the two optimization criteria—number of rows and total height—for both NORD and ORD. Surprisingly, we show that the minimum-height ORD may require Ω(log n/ log log n) times as many rows as the minimum-row ORD. The proof of the matching upper bound employs a novel application of information entropy.

Original languageEnglish
Title of host publicationLATIN 2020
Subtitle of host publicationTheoretical Informatics - 14th Latin American Symposium 2021, Proceedings
EditorsYoshiharu Kohayakawa, Flávio Keidi Miyazawa
PublisherSpringer Science and Business Media Deutschland GmbH
Pages258-270
Number of pages13
ISBN (Print)9783030617912
DOIs
Publication statusPublished - 2020
Event14th Latin American Symposium on Theoretical Informatics, LATIN 2020 - Sao Paulo, Brazil
Duration: 5 Jan 20218 Jan 2021

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume12118 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference14th Latin American Symposium on Theoretical Informatics, LATIN 2020
CountryBrazil
CitySao Paulo
Period5/01/218/01/21

Keywords

  • Linear layouts
  • Packing

Fingerprint Dive into the research topics of 'Ordered Strip Packing'. Together they form a unique fingerprint.

Cite this