Samenvatting
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.
Originele taal-2 | Engels |
---|---|
Titel | LATIN 2020 |
Subtitel | Theoretical Informatics - 14th Latin American Symposium 2021, Proceedings |
Redacteuren | Yoshiharu Kohayakawa, Flávio Keidi Miyazawa |
Uitgeverij | Springer |
Pagina's | 258-270 |
Aantal pagina's | 13 |
ISBN van geprinte versie | 9783030617912 |
DOI's | |
Status | Gepubliceerd - 2020 |
Evenement | 14th Latin American Symposium on Theoretical Informatics, LATIN 2020 - Sao Paulo, Brazilië Duur: 5 jan. 2021 → 8 jan. 2021 |
Publicatie series
Naam | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|
Volume | 12118 LNCS |
ISSN van geprinte versie | 0302-9743 |
ISSN van elektronische versie | 1611-3349 |
Congres
Congres | 14th Latin American Symposium on Theoretical Informatics, LATIN 2020 |
---|---|
Land/Regio | Brazilië |
Stad | Sao Paulo |
Periode | 5/01/21 → 8/01/21 |
Financiering
W. Sonke, B. Speckmann and K. Verbeek—Partially supported by the Netherlands Organisation for Scientific Research (NWO) under project no. 639.023.208 (W.S. and B.S.) and no. 639.021.541 (K.V.).