Ordered Strip Packing

K. Buchin; D. Kosolobov; W. Sonke; B. Speckmann; K. Verbeek

doi:10.1007/978-3-030-61792-9_21

Ordered Strip Packing

K. Buchin, D. Kosolobov, W. Sonke, B. Speckmann, K. Verbeek

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/Congresprocedure › Conferentiebijdrage › Academic › peer review

150 Downloads (Pure)

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	https://doi.org/10.1007/978-3-030-61792-9_21
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.).

Toegang tot document

10.1007/978-3-030-61792-9_21

ordered_strip_packing_2019Finale auteursversie , 816 KB

Andere bestanden en links

Link to publication in Scopus

Citeer dit

Buchin, K., Kosolobov, D., Sonke, W., Speckmann, B., & Verbeek, K. (2020). Ordered Strip Packing. In Y. Kohayakawa, & F. K. Miyazawa (editors), LATIN 2020: Theoretical Informatics - 14th Latin American Symposium 2021, Proceedings (blz. 258-270). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 12118 LNCS). Springer. https://doi.org/10.1007/978-3-030-61792-9_21

Buchin, K. ; Kosolobov, D. ; Sonke, W. et al. / Ordered Strip Packing. LATIN 2020: Theoretical Informatics - 14th Latin American Symposium 2021, Proceedings. redacteur / Yoshiharu Kohayakawa ; Flávio Keidi Miyazawa. Springer, 2020. blz. 258-270 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{899b3cbc825242d9a1c4cf21464d04e3,

title = "Ordered Strip Packing",

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.",

keywords = "Linear layouts, Packing",

author = "K. Buchin and D. Kosolobov and W. Sonke and B. Speckmann and K. Verbeek",

year = "2020",

doi = "10.1007/978-3-030-61792-9_21",

language = "English",

isbn = "9783030617912",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer",

pages = "258--270",

editor = "Yoshiharu Kohayakawa and Miyazawa, {Fl{\'a}vio Keidi}",

booktitle = "LATIN 2020",

address = "Germany",

note = "14th Latin American Symposium on Theoretical Informatics, LATIN 2020 ; Conference date: 05-01-2021 Through 08-01-2021",

}

Buchin, K, Kosolobov, D, Sonke, W , Speckmann, B & Verbeek, K 2020, Ordered Strip Packing. in Y Kohayakawa & FK Miyazawa (uitgave), LATIN 2020: Theoretical Informatics - 14th Latin American Symposium 2021, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 12118 LNCS, Springer, blz. 258-270, 14th Latin American Symposium on Theoretical Informatics, LATIN 2020, Sao Paulo, Brazilië, 5/01/21. https://doi.org/10.1007/978-3-030-61792-9_21

Ordered Strip Packing. / Buchin, K.; Kosolobov, D.; Sonke, W. et al.
LATIN 2020: Theoretical Informatics - 14th Latin American Symposium 2021, Proceedings. uitgave / Yoshiharu Kohayakawa; Flávio Keidi Miyazawa. Springer, 2020. blz. 258-270 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 12118 LNCS).

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/Congresprocedure › Conferentiebijdrage › Academic › peer review

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

T2 - 14th Latin American Symposium on Theoretical Informatics, LATIN 2020

Y2 - 5 January 2021 through 8 January 2021

ER -

Buchin K, Kosolobov D, Sonke W , Speckmann B , Verbeek K. Ordered Strip Packing. In Kohayakawa Y, Miyazawa FK, redacteurs, LATIN 2020: Theoretical Informatics - 14th Latin American Symposium 2021, Proceedings. Springer. 2020. blz. 258-270. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-030-61792-9_21

Ordered Strip Packing

Samenvatting

Publicatie series

Congres

Financiering

Toegang tot document

Andere bestanden en links

Vingerafdruk

Citeer dit