TY - GEN
T1 - Ordered Strip Packing
AU - Buchin, K.
AU - Kosolobov, D.
AU - Sonke, W.
AU - Speckmann, B.
AU - Verbeek, K.
PY - 2020
Y1 - 2020
N2 - 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.
AB - 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.
KW - Linear layouts
KW - Packing
UR - http://www.scopus.com/inward/record.url?scp=85097717926&partnerID=8YFLogxK
U2 - 10.1007/978-3-030-61792-9_21
DO - 10.1007/978-3-030-61792-9_21
M3 - Conference contribution
AN - SCOPUS:85097717926
SN - 9783030617912
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 258
EP - 270
BT - LATIN 2020
A2 - Kohayakawa, Yoshiharu
A2 - Miyazawa, Flávio Keidi
PB - Springer Science and Business Media Deutschland GmbH
T2 - 14th Latin American Symposium on Theoretical Informatics, LATIN 2020
Y2 - 5 January 2021 through 8 January 2021
ER -