Ordered Strip Packing

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

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer 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-2Engels
TitelLATIN 2020
SubtitelTheoretical Informatics - 14th Latin American Symposium 2021, Proceedings
RedacteurenYoshiharu Kohayakawa, Flávio Keidi Miyazawa
UitgeverijSpringer
Pagina's258-270
Aantal pagina's13
ISBN van geprinte versie9783030617912
DOI's
StatusGepubliceerd - 2020
Evenement14th Latin American Symposium on Theoretical Informatics, LATIN 2020 - Sao Paulo, Brazilië
Duur: 5 jan. 20218 jan. 2021

Publicatie series

NaamLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume12118 LNCS
ISSN van geprinte versie0302-9743
ISSN van elektronische versie1611-3349

Congres

Congres14th Latin American Symposium on Theoretical Informatics, LATIN 2020
Land/RegioBrazilië
StadSao Paulo
Periode5/01/218/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.).

Vingerafdruk

Duik in de onderzoeksthema's van 'Ordered Strip Packing'. Samen vormen ze een unieke vingerafdruk.

Citeer dit